Geodesic
Minimum survivable graphs with bounded distance increase
Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 1.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2003_6_1_a7,
     author = {Djelloul, Selma and Kouider, Mekkia},
     title = {Minimum survivable graphs with bounded distance increase},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {6},
     number = {1},
     year = {2003-2004},
     doi = {10.46298/dmtcs.338},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.338/}
}
TY  - JOUR
AU  - Djelloul, Selma
AU  - Kouider, Mekkia
TI  - Minimum survivable graphs with bounded distance increase
JO  - Discrete mathematics & theoretical computer science
PY  - 2003-2004
VL  - 6
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.338/
DO  - 10.46298/dmtcs.338
LA  - en
ID  - DMTCS_2003_6_1_a7
ER  - 
%0 Journal Article
%A Djelloul, Selma
%A Kouider, Mekkia
%T Minimum survivable graphs with bounded distance increase
%J Discrete mathematics & theoretical computer science
%D 2003-2004
%V 6
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.338/
%R 10.46298/dmtcs.338
%G en
%F DMTCS_2003_6_1_a7
Djelloul, Selma; Kouider, Mekkia. Minimum survivable graphs with bounded distance increase. Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 1. doi : 10.46298/dmtcs.338. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.338/

Cité par Sources :