The Complexity of Reliability Computations in Planar and Acyclic Graphs
- 1 August 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (3) , 694-702
- https://doi.org/10.1137/0215050
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- Polyhedral Combinatorics and Network ReliabilityMathematics of Operations Research, 1986
- An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed NetworksOperations Research, 1984
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is ConnectedSIAM Journal on Computing, 1983
- Calculating bounds on reachability and connectedness in stochastic networksNetworks, 1983
- Complexity of network reliability computationsNetworks, 1980
- New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex NetworksIEEE Transactions on Reliability, 1978
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- Computing the Reliability of Complex NetworksSIAM Journal on Applied Mathematics, 1977
- Sequential Bounding of the Reliability of a Stochastic NetworkOperations Research, 1976
- The Planar Hamiltonian Circuit Problem is NP-CompleteSIAM Journal on Computing, 1976