Edge-packings of graphs and network reliability (Q1111461)

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 \textit{V. P. Polesski} [Prob. Inf. Transmission 7, 165-171 (1971)], and the application of s,t-paths has been studied by \textit{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.