Computational Complexity of Network Reliability Analysis: An Overview
- 1 January 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Reliability
- Vol. 35 (3) , 230-239
- https://doi.org/10.1109/tr.1986.4335422
Abstract
This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures for stochastic networks. We show how these problems are related to the more familiar computational network problems of recognizing certain subnetworks, finding optimal subnetworks, and counting certain subnetworks. We use these relationships to show that the k-terminal, the 2-terminal, and the all-terminal network reliability analysis problems are at least as hard as the renowned set of computationally difficult problems, NP-Complete. Finally, we discuss the impact of these results on how one should approach problem solving in this area.Keywords
This publication has 26 references indexed in Scilit:
- Network reliability analysis using 2‐connected digraph reductionsNetworks, 1985
- Series‐parallel reduction for difficult measures of network reliabilityNetworks, 1981
- A recursive algorithm for finding reliability measures related to the connection of nodes in a graphNetworks, 1980
- Complexity of network reliability computationsNetworks, 1980
- The minimum number of edges and vertices in a graph with edge connectivity 𝑛 and 𝑚 𝑛-bondsBulletin of the American Mathematical Society, 1974
- Recursive analysis of network reliabilityNetworks, 1973
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- Computer communication network design: Experience with theory and practiceNetworks, 1972
- Network reliability analysis: Part INetworks, 1971
- Multi-Component Systems and Structures and Their ReliabilityTechnometrics, 1961