Computational complexity of network reliability analysis: An overview. (English) Zbl 0602.90061

Ball, Michael O.

IEEE Trans. Reliab. 35, 230-239 (1986).

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.

MSC:

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

Keywords:

computational complexity; network reliability analysis; stochastic networks; optimal subnetworks