Computing Network Reliability in Time Polynomial in the Number of Cuts

J. Scott Provan and Michael O. Ball
Additional contact information
J. Scott Provan: National Bureau of Standards, Washington, D. C. and University of North Carolina, Chapel Hill, North Carolina
Michael O. Ball: University of Maryland, College Park, Maryland

Operations Research, 1984, vol. 32, issue 3, 516-526

Abstract: We present a new algorithm that computes the probability that there is an operating path from a node s to a node t in a stochastic network. The computation time of this algorithm is bounded by a polynomial in the number of ( s , t )-cuts in the network. We also examine the complexity of other connectedness reliability problems with respect to the number of cutsets and pathsets in the network. These problems are distinguished as either having algorithms that are polynomial in the number of such sets, or having no such algorithms unless P = NP .

Keywords: 488 network reliability; 723 connectedness reliability in networks (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.3.516 (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:516-526

Access Statistics for this article

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