Geodesic
Diameter Constrained Reliability of Ladders and Spanish Fans
Yugoslav journal of operations research, Tome 26 (2016) no. 1, p. 17 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Abstract: We are given a graph $G = (V,E)$, terminal set $K \subseteq V$ and diameter $d$ > 0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short) is the probability that the $K$-diameter is not greater than $d$ in the subgraph induced by non-failed links. The contributions of this paper are two-fold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminals $k$ = |$K$| and diameter $d$. Here, we prove that if $d$ > 2, the problem is NP-Hard when $K = V$, and second, we compute the DCR efficiently for ladders and Spanish fans.
Classification : 90B15, 90B18, 90B25.
Keywords: Diameter Constrained Reliability, Computational Complexity, Graph Theory. 
@article{YJOR_2016_26_1_a1,
     author = {H\'ector Cancela and Franco Robledo and Pablo Romero and Pablo Sartor},
     title = {Diameter {Constrained} {Reliability} of {Ladders} and {Spanish} {Fans}},
     journal = {Yugoslav journal of operations research},
     pages = {17 },
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a1/}
}
TY  - JOUR
AU  - Héctor Cancela
AU  - Franco Robledo
AU  - Pablo Romero
AU  - Pablo Sartor
TI  - Diameter Constrained Reliability of Ladders and Spanish Fans
JO  - Yugoslav journal of operations research
PY  - 2016
SP  - 17 
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a1/
LA  - en
ID  - YJOR_2016_26_1_a1
ER  - 
%0 Journal Article
%A Héctor Cancela
%A Franco Robledo
%A Pablo Romero
%A Pablo Sartor
%T Diameter Constrained Reliability of Ladders and Spanish Fans
%J Yugoslav journal of operations research
%D 2016
%P 17 
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a1/
%G en
%F YJOR_2016_26_1_a1
Héctor Cancela; Franco Robledo; Pablo Romero; Pablo Sartor. Diameter Constrained Reliability of Ladders and Spanish Fans. Yugoslav journal of operations research, Tome 26 (2016) no. 1, p. 17 . http://geodesic.mathdoc.fr/item/YJOR_2016_26_1_a1/