Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958995
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:59:39 PM
Last modification on : Thursday, July 8, 2021 - 3:47:57 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:13:01 PM

File

dm060110.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

270

Files downloads

915