Minimum survivable graphs with bounded distance increase

Abstract : We study in graphs properties related to fault-tolerance in case a node fails. A graph G is k-self-repairing, where k is a non-negative integer, if after the removal of any vertex no distance in the surviving graph increases by more than k. In the design of interconnection networks such graphs guarantee good fault-tolerance properties. We give upper and lower bounds on the minimum number of edges of a k-self-repairing graph for prescribed k and n, where n is the order of the graph. We prove that the problem of finding, in a k-self-repairing graph, a spanning k-self-repairing subgraph of minimum size is NP-Hard.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.123-132
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958995
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:59:39
Dernière modification le : mardi 24 avril 2018 - 13:55:39
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:13:01

Fichier

dm060110.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958995, version 1

Collections

Citation

Selma Djelloul, Mekkia Kouider. Minimum survivable graphs with bounded distance increase. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.123-132. 〈hal-00958995〉

Partager

Métriques

Consultations de la notice

195

Téléchargements de fichiers

255