Selma Djelloul ; Mekkia Kouider - Minimum survivable graphs with bounded distance increase

dmtcs:338 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, Vol. 6 no. 1 -
Minimum survivable graphs with bounded distance increase

Authors: Selma Djelloul 1; Mekkia Kouider 1

  • 1 Laboratoire de Recherche en Informatique

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.

Volume: Vol. 6 no. 1
Published on: January 1, 2003
Imported on: March 26, 2015
Keywords: distance,fault-tolerance,spanning subgraph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/0012-365x(94)00255-h
  • 10.1016/0012-365x(94)00255-h
On two-connected subgraph polytopes

Consultation statistics

This page has been seen 541 times.
This article's PDF has been downloaded 194 times.