Geodesic
On the Reliability of Series-Parallel Networks in Grid Graphs
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 9 (2009) no. 2, pp. 3-14 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider a directed rectangular grid with one source and one sink such that its arcs are directed either to the right or up and have an equal functioning probability. In this paper under network reliability we assume the probability that there is at least one path containing no failed edge from the source to the sink. Because the problem of the grid reliability calculation is NP-hard, the estimates of the network reliability that can be computed in polynomial time are of interest. This paper deals with the problem of finding the most reliable series-parallel network, its reliability will be the lower bound of the grid reliability. 
@article{VNGU_2009_9_2_a0,
     author = {T. A. Aldyn-ool and A. I. Erzin},
     title = {On the {Reliability} of {Series-Parallel} {Networks} in {Grid} {Graphs}},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {3--14},
     year = {2009},
     volume = {9},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2009_9_2_a0/}
}
TY  - JOUR
AU  - T. A. Aldyn-ool
AU  - A. I. Erzin
TI  - On the Reliability of Series-Parallel Networks in Grid Graphs
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2009
SP  - 3
EP  - 14
VL  - 9
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VNGU_2009_9_2_a0/
LA  - ru
ID  - VNGU_2009_9_2_a0
ER  - 
%0 Journal Article
%A T. A. Aldyn-ool
%A A. I. Erzin
%T On the Reliability of Series-Parallel Networks in Grid Graphs
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2009
%P 3-14
%V 9
%N 2
%U http://geodesic.mathdoc.fr/item/VNGU_2009_9_2_a0/
%G ru
%F VNGU_2009_9_2_a0
T. A. Aldyn-ool; A. I. Erzin. On the Reliability of Series-Parallel Networks in Grid Graphs. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 9 (2009) no. 2, pp. 3-14. http://geodesic.mathdoc.fr/item/VNGU_2009_9_2_a0/

[1] Rosenthal A., Computing Reliability of Complex Systems, Doctoral Thesis, Dept. of Electrical Engineering and Computer Science, Univ. of California, Berkeley, 1974

[2] Valiant L. G., “The Complexity of Enumeration and Reliability Problems”, SIAM J. Comput., 8:3 (1979), 410–421 | DOI | MR | Zbl

[3] Provan J. S., “The Complexity of Reliability Computations in Planar and Acyclic Praphs”, SIAM J. Comput., 15:3 (1986), 694–702 | DOI | MR | Zbl

[4] Garey M. R., Johnson D. S., Computers and Intractability: a Guide to the Theory of $NP$-Completeness, W. H. Freeman, San Francisco, 1979 | MR | Zbl

[5] Abraham J. A., “An Improved Algorithm for Network Reliability”, IEEE Trans. Reliability, R-28:1 (1979), 58–61 | DOI

[6] Mur E., Shennon K., “Nadezhnye skhemy iz nenadezhnykh rele”, Kiberneticheskii sb., 1, Inostr. lit., M., 1960, 109–148

[7] Shooman A. M., “Algorithms for Network Reliability and Connection Availability Analysis”, Electro/95 International. Professional Program Proceedings, 1995, 309–333

[8] Rosenthal A., “Computing the Reliability of Complex Networks”, SIAM J. Appl. Math., 32:2 (1977), 384–393 | DOI | MR | Zbl

[9] Gnedenko B. V., Kurs teorii veroyatnostei, Nauka, M., 1988 | MR

[10] Rodionova O. K., Issledovanie i razrabotka metodov analiza i sinteza optimalno-svyaznykh informatsionnykh setei, Dis. \ldots kand. tekhn. nauk, Novosibirsk, 2003

[11] Luby M. G., Monte-Carlo Methods for Estimating System Reliability, Tech. Rep. 84/168, Computer Science Division, Univ. of California, Berkeley, 1982

[12] Rainshke K., Ushakov I. A., Otsenka nadezhnosti sistem s ispolzovaniem grafov, Radio i svyaz, M., 1988 | MR

[13] Polesskii V. P., “A Lower Boundary for the Reliability of Information Networks”, Prob. Inf. Trans., 7:2 (1971), 165–171 | MR

[14] Misra K. B., “An Algorithm for the Reliability Evaluation of Redundant Networks”, IEEE Trans. Reliability, R-19:4 (1970), 146–151 | DOI

[15] Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. 1, Nauka, M., 1974