Complexity of network reliability computations

Abstract

Abstract This paper considers the difficulty of computing several measures of network reliability on directed and undirected networks. Results concerning the NP‐difficulty of several network reliability analysis problems are unified and in several cases generalized to wider classes of measures. Reductions are also given that relate network reliability problems on directed and undirected networks and problems with and without node failures.