zbMATH — the first resource for mathematics

Computational complexity of network reliability analysis: An overview. (English) Zbl 0602.90061
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.

90B25 Reliability, availability, maintenance, inspection in operations research
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
90B20 Traffic problems in operations research
Full Text: DOI