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/