An algorithm for reliability analysis of planar graphs
- 1 December 1986
- Vol. 16 (4) , 411-422
- https://doi.org/10.1002/net.3230160407
Abstract
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.Keywords
This publication has 11 references indexed in Scilit:
- Four pages are necessary and sufficient for planar graphsPublished by Association for Computing Machinery (ACM) ,1986
- The Complexity of Reliability Computations in Planar and Acyclic Graphs.Published by Defense Technical Information Center (DTIC) ,1984
- Finding small simple cycle separators for 2-connected planar graphs.Published by Association for Computing Machinery (ACM) ,1984
- A recursive algorithm for finding reliability measures related to the connection of nodes in a graphNetworks, 1980
- Complexity of network reliability computationsNetworks, 1980
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Computing the Reliability of Complex NetworksSIAM Journal on Applied Mathematics, 1977
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- Advanced CombinatoricsPublished by Springer Nature ,1974