A Survey of Network Reliability and Domination Theory

Avinash Agrawal and Richard E. Barlow
Additional contact information
Avinash Agrawal: Tymnet, Inc., San Jose, California
Richard E. Barlow: University of California, Berkeley, California

Operations Research, 1984, vol. 32, issue 3, 478-492

Abstract: We present a brief survey of the current state of the art in network reliability. We survey only exact methods and do not consider Monte Carlo methods. Most network reliability problems are, in the worst case, NP-hard and are, in a sense, more difficult than many standard combinatorial optimization problems. Nevertheless, there are, in fact, linear and polynomial time algorithms for network reliability problems of special structure. We review general methods for network reliability computation and discuss the central role played by domination theory in network reliability computational complexity. We also point out the connection with the more general problem of computing the reliability of coherent structures. The class of coherent structures contains both directed and undirected networks as well as logic (or fault) trees without not gates. This topic is a rich area for further research.

Keywords: 481 networks/graphs; 570 stochastic model applications; 721 reliability (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.3.478 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:3:p:478-492

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().