Counting almost minimum cutsets with reliability applications.(English)Zbl 0631.90029
The number \(n_ i\) of i-edge network cutsets in a graph is an important parameter in reliability analysis. Using a theorem ofM. V. Lomonosov andV. P. Polesskij [Probl. Peredaci Inform. 8, No.2, 47-53 (1972;Zbl 0272.94019)] andM. O. Ball andJ. S. Provan [SIAM J. Alg. Discrete Methods 3, 166-181 (1982;Zbl 0504.05053)] have shown that the number \(n_ c\) of minimum cardinality network cutsets can be determined in polynomial time. This paper gives a polynomial time algorithm for determining \(n_{c+k}\) for any fixed k, as a special case of counting cuts of specified maximum weight in an edge-weighted graph. The resulting improvement in existing reliability bounds is shown to be substantial.
MSC:
| 90B25 | Reliability, availability, maintenance, inspection in operations research |
| 68Q25 | Analysis of algorithms and problem complexity |
| 94C15 | Applications of graph theory to circuits and networks |
Keywords:
probabilistic graph;network reliability;inclusion-exclusion;network cutsets in a graph;minimum cardinality network cutsets;polynomial time algorithm;edge-weighted graph;reliability boundsCite
Full Text:DOI
References:
| [1] | M.O. Ball, ”Computing network reliability,”Operations Research 27 (1979) 823–838. ·Zbl 0412.90030 ·doi:10.1287/opre.27.4.823 |
| [2] | M.O. Ball, ”Complexity of network reliability computations,”Networks 10 (1980) 153–165. ·Zbl 0443.90038 ·doi:10.1002/net.3230100206 |
| [3] | M.O. Ball and J.S. Provan, ”Calculating bounds on reachability and connectedness in stochastic networks,”Networks 13 (1983) 253–278 ·Zbl 0569.68053 ·doi:10.1002/net.3230130210 |
| [4] | M.O. Ball and J.S. Provan, ”Bounds on the reliability polynomial for shellable independence systems,”SIAM Journal of Algebraic and Discrete Methods 3 (1982) 166–181. ·Zbl 0504.05053 ·doi:10.1137/0603016 |
| [5] | R.E. Bixby, ”The minimum number of edges and vertices in a graph with edge connectivityn andm n-bonds,”Networks 5 (1975) 253–298. ·Zbl 0314.05106 |
| [6] | J.A. Bondy and U.S.R. Murty,Graph Theory with Applications (North-Holland, Amsterdam, 1976). ·Zbl 1226.05083 |
| [7] | T.B. Brecht and C.J. Colbourn, ”Lower bounds on two-terminal network reliability,” to appear inDiscrete Applied Mathematics. ·Zbl 0665.90036 |
| [8] | R.L. Brooks, C.A.B. Smith, A.H. Stone and W.T. Tutte, ”The dissection of rectangles into squares,”Duke Mathematical Journal 7 (1940) 312–340. ·Zbl 0024.16501 ·doi:10.1215/S0012-7094-40-00718-9 |
| [9] | J.A. Buzacott, ”A recursive algorithm for finding reliability measures related to the connection of nodes in a graph,”Networks 10 (1980) 311–327. ·Zbl 0454.68074 ·doi:10.1002/net.3230100404 |
| [10] | C.J. Colbourn, ”The reliability polynomial,”Ars Combinatoria 21A (1986) 31–58. ·Zbl 0589.90032 |
| [11] | C.J. Colboun and D.D. Harms, ”Bounding all-terminal reliability in computer networks,”Networks, to appear. |
| [12] | H. Frank and W. Chou, ”Network properties of the ARPA computer network,”Network 4 (1974) 213–239. ·doi:10.1002/net.3230040303 |
| [13] | D. D. Harms, ”An investigation into bounds on network reliability,” M.Sc. Thesis, Department of Computational Science, University of Saskatchewan, 1984. |
| [14] | I.M. Jacobs, ”Connectivity in probabilistic graphs,” Tech. Report #356, MIT, Electronics Research Laboratory, (Cambridge, Mass., 1959). |
| [15] | E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart, and Winston, New York, 1976). ·Zbl 0413.90040 |
| [16] | M.V. Lomonosov and V.P. Polesskii, ”Lower bounds of network reliability,”Problems of Information Transmission 8 (1972) 118–123. ·Zbl 0335.05124 |
| [17] | J.S. Provan and M.O. Ball, ”The complexity of counting cuts and of computing the probability that the graph is connected,”SIAM Journal on Computing 12 (1983) 777–788. ·Zbl 0524.68041 ·doi:10.1137/0212053 |
| [18] | A. Ramesh, M.O. Ball and C.J. Colbourn, ”Bounding all-terminal reliability in planar networks,”Annals of Discrete Mathematics 33 (1987) 261–273. ·Zbl 0627.05025 |
| [19] | A. Rosenthal, ”Computing the reliability of complex networks,”SIAM Journal of Applied Mathematics 32 (1977) 384–393. ·Zbl 0379.90048 ·doi:10.1137/0132031 |
| [20] | A. Satyanarayana and A. Prabhakar, ”New topological formula and rapid algorithm for reliability analysis of complex networks,”IEEE: Transactions on reliability R-27 (1978) 82–100. ·Zbl 0409.90039 ·doi:10.1109/TR.1978.5220266 |
| [21] | L.G. Valiant, ”The complexity of enumeration and reliability problems,”SIAM Journal on Computing 8 (1979) 410–421. ·Zbl 0419.68082 ·doi:10.1137/0208032 |
| [22] | R. Van Slyke and H. Frank, ”Network reliability analysis: Part l,”Networks 1 (1972) 279–290. ·Zbl 0239.94041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
