Edge-packings of graphs and network reliability. (English) Zbl 0657.90041
The reliability of a network can be efficiently bounded using graph- theoretical techniques based on edge-packing. We examine the application of combinatorial theorems on edge-packing spanning trees, s,t-paths, and s,t-cuts to the determination of reliability bounds. The application of spanning trees has been studied by V. P. Polesski [Prob. Inf. Transmission 7, 165-171 (1971)], and the application of s,t-paths has been studied by T. B. Brecht and the author [Networks 16, No.4, 369-380 (1986; Zbl 0644.90044)]. The use of edge-packings of s,t-cutsets has not been previously examined. We compare the resulting bounds with known bounds produced by different techniques, and establish that the edge-packing bounds often produce a substantial improvement. We also establish that three other edge-packing problems arising in reliability bounding are NP-complete, namely edge-packing by network cutsets, Steiner trees, and Steiner cutsets.
MSC:
| 90B25 | Reliability, availability, maintenance, inspection in operations research |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
reliability of a network; graph-theoretical techniques; edge-packing; spanning trees; reliability boundsCitations:
Zbl 0644.90044References:
| [1] | Ball, M. O., Complexity of network reliability computations, Networks, 10, 153-165 (1980) · Zbl 0443.90038 |
| [2] | Ball, M. O.; Provan, J. S., Bounds on the reliability polynomial for shellable independence systems, SIAM J. Alg. Disc. Meth., 3, 166-181 (1982) · Zbl 0504.05053 |
| [3] | Ball, M. O.; Provan, J. S., Calculating bounds on reachability and connectedness in stochastic networks, Networks, 13, 253-278 (1983) · Zbl 0569.68053 |
| [4] | T.B. Brecht and C.J. Colbourn, Lower bounds for two-terminal network reliability, Discrete Applied Math., to appear.; T.B. Brecht and C.J. Colbourn, Lower bounds for two-terminal network reliability, Discrete Applied Math., to appear. · Zbl 0665.90036 |
| [5] | Brecht, T. B.; Colbourn, C. J., Improving reliability bounds in computer networks, Networks, 16, 369-380 (1986) · Zbl 0644.90044 |
| [6] | Colbourn, C. J., The combinatorics of network reliability (1987), Oxford University Press: Oxford University Press Oxford and New York |
| [7] | Colbourn, C. J.; Harms, D. D., Bounds for all-terminal reliability in computer networks, Networks, 18, 1-12 (1988) |
| [8] | Edmonds, J., Minimum partition of a matroid into independent subsets, J. Res. NBS, 69B, 67-72 (1965) · Zbl 0192.09101 |
| [9] | Fulkerson, D. R., Networks, frames, blocking systems, Math. Decision Sciences, 303-334 (1968) · Zbl 0182.53402 |
| [10] | Fulkerson, D. R., Blocking and anti-blocking pairs of polyhedra, Math. Prog., 1, 168-194 (1972) · Zbl 0254.90054 |
| [11] | Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman and Sons · Zbl 0411.68039 |
| [12] | Holyer, I., The NP-completeness of edge-colouring, SIAM J. Computing, 10, 718-720 (1981) · Zbl 0473.68034 |
| [13] | Leven, D.; Galil, Z., NP-completeness of finding the chromatic index of regular graphs, J. Algorithms, 4, 35-44 (1983) · Zbl 0509.68037 |
| [14] | Lomonosov, M. V.; Polesskii, V. P., An upper bound for the reliability of information networks, Prob. Inf. Transmission, 7, 337-339 (1971) · Zbl 0323.90024 |
| [15] | Lomonosov, M. V.; Polesskii, V. P., Lower bound of network reliability, Prob. Inf. Transmission, 8, 118-123 (1972) · Zbl 0335.05124 |
| [16] | Menger, K., Zur allgemeine Kurventheorie, Fund. Math., 10, 96-115 (1927) · JFM 53.0561.01 |
| [17] | Nash-Williams, C. St. J.A., Edge-disjoint spanning trees of finite graphs, J. London Math. Soc., 36, 445-450 (1961) · Zbl 0102.38805 |
| [18] | Polesskii, V. P., A lower boundary for the reliability of information networks, Prob. Inf. Transmission, 7, 165-171 (1971) |
| [19] | Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Computing, 12, 777-788 (1983) · Zbl 0524.68041 |
| [20] | Ramanathan, A.; Colbourn, C. J., Bounds for all-terminal reliability via arc-packing, Ars Combinatoria, 23A, 229-236 (1987) · Zbl 0642.05034 |
| [21] | Robacker, J. T., Min-max theorems on shortest chains and disjunct cuts of a network (1956), The RAND Corporation, RM-1660-PR |
| [22] | Tutte, W. T., On the problem of decomposing a graph into \(n\) connected factors, J. London Math. Soc., 36, 221-230 (1961) · Zbl 0096.38001 |
| [23] | Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Computing, 8, 410-421 (1979) · Zbl 0419.68082 |
| [24] | Van Slyke, R. M.; Frank, H., Network reliability analysis I, Networks, 1, 279-290 (1972) · 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.
