Premium
Complexity of network reliability computations
Author(s) -
Ball Michael O.
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100206
Subject(s) - reliability (semiconductor) , computer science , node (physics) , directed graph , undirected graph , computation , theoretical computer science , mathematical optimization , graph , mathematics , algorithm , power (physics) , physics , structural engineering , quantum mechanics , engineering
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.