Edge-packings of graphs and network reliability
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.
- Blocking and anti-blocking pairs of polyhedra
- Bounds on the Reliability Polynomial for Shellable Independence Systems
- Calculating bounds on reachability and connectedness in stochastic networks
- Complexity of network reliability computations
- Edge-Disjoint Spanning Trees of Finite Graphs
- scientific article; zbMATH DE number 4045783 (Why is no real title available?)
- scientific article; zbMATH DE number 3506434 (Why is no real title available?)
- scientific article; zbMATH DE number 3523603 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3290885 (Why is no real title available?)
- Improving reliability bounds in computer networks
- Lower bounds on two-terminal network reliability
- Minimum partition of a matroid into independent subsets
- Network reliability analysis: Part I
- NP completeness of finding the chromatic index of regular graphs
- On the Problem of Decomposing a Graph into n Connected Factors
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- The NP-Completeness of Edge-Coloring
- A note on bounding \(k\)-terminal reliability
- On the k-cut subgraph polytope
- Sixty years of network reliability
- Practical sequential bounds for approximating two-terminal reliability
- Packing \([1, \Delta ]\)-factors in graphs of small degree
- Fast computation of bounds for two-terminal network reliability
- Edge-disjoint packing of stars and cycles
- scientific article; zbMATH DE number 4045783 (Why is no real title available?)
- scientific article; zbMATH DE number 205333 (Why is no real title available?)
- A branch-price-and-cut algorithm for packing cuts in undirected graphs
- scientific article; zbMATH DE number 975420 (Why is no real title available?)
- scientific article; zbMATH DE number 5176323 (Why is no real title available?)
- Reliable assignments of processors to tasks and factoring on matroids
- A polynomial-time simplex method for the maximum \(k\)-flow problem
This page was built for publication: Edge-packings of graphs and network reliability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111461)
