| Title: |
Computing Network Reliability in Time Polynomial in the Number of Cuts. |
| Authors: |
Provan, J. Scott1,2; Ball, Michael O.3 |
| Source: |
Operations Research. May/Jun1984, Vol. 32 Issue 3, p516. 11p. |
| Subject Terms: |
*Algorithms; *Stochastic processes; *Network analysis (Planning); *Probability theory; *Reliability in engineering; *Stochastic analysis; Communication network analysis; Polynomials |
| 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 am distinguished as either having algorithms that are polynomial in the number of such sets, or having no such algorithms unless P = NP. [ABSTRACT FROM AUTHOR] |
| : |
Copyright of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Business Source Premier |