×
Bienstock, Daniel

An algorithm for reliability analysis of planar graphs. (English) Zbl 0643.90030

Networks 16, No. 4, 411-422 (1986).
Summary: We give an algorithm for the computation of K-terminal reliability in planar graphs, whose worst-case complexity is strictly exponential in the square root of the total number of nodes.

Cited in 1 Review
Cited in 2 Documents

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
90B10 Deterministic network models in operations research

Keywords:

computation of K-terminal reliability; planar graphs; worst-case complexity
Cite Review PDF
Full Text: DOI Link

References:

[1] Ball, Networks 10 pp 153– (1980)
[2] Some lattice-theoretic tools for network reliability analysis. Working paper #21-85-86, GSIA, Carnegie-Mellon University (1986).
[3] Booth, J. Comput. Syst. Sci. 13 pp 335– (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[4] Buzacott, Networks 10 pp 311– (1980)
[5] Advanced Combinatories. D. Reidel Publishing Co., Dolrdrecht, Holland (1974). · doi:10.1007/978-94-010-2196-8
[6] and , Decomposition techniques for evaluating network reliability. IBM report RC5923 (1976).
[7] , and , On nontrivial separators fo. k-page graphs and simulations by nondeterministic one-tape turing machines. Proc. of 18th ACM Symp. on Theory of Computing, (1986).
[8] Hopcroft, J. Assoc. Comput. Mach. 21 pp 549– (1974) · Zbl 0307.68025 · doi:10.1145/321850.321852
[9] Lipton, SIAM J. Appl. Math. 36 pp 177– (1979)
[10] Finding small simple cycle separators for 2-connected planar graphs. Proc. of 16th ACM Symp. on Theory of Computing (1984) 376–382.
[11] The complexity of reliability computations in planar and acyclic graphs. Technical Report No. UNC/ORSA/TR-83/12, Univ. of North Carolina at Chapel Hill (1984).
[12] Rosenthal, SIAM J. Appl. Math. 32 pp 384– (1977)
[13] Four pages are necessary and sufficient. Proc. of 18th ACM Symp. on Theory of Computing (1986).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.