Edge-packings of graphs and network reliability
type: Item
instance of: scholarly article
title: Edge-packings of graphs and network reliability
zbMATH Open document ID: 0657.90041
DOI: 10.1016/0012-365X(88)90193-8
author: Charles J. Colbourn
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4074786
zbMATH Keywords: reliability of a network
zbMATH Keywords: graph-theoretical techniques
zbMATH Keywords: edge-packing
zbMATH Keywords: spanning trees
zbMATH Keywords: reliability bounds
MaRDI profile type: Publication
cites work: Complexity of network reliability computations
cites work: Bounds on the Reliability Polynomial for Shellable Independence Systems
cites work: Calculating bounds on reachability and connectedness in stochastic networks
cites work: Lower bounds on two-terminal network reliability
cites work: Improving reliability bounds in computer networks
cites work: Minimum partition of a matroid into independent subsets
cites work: Q5572841
cites work: Blocking and anti-blocking pairs of polyhedra
cites work: Q4198056
cites work: The NP-Completeness of Edge-Coloring
cites work: NP completeness of finding the chromatic index of regular graphs
cites work: Q4086956
cites work: Q4101857
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
cites work: Q3783317
cites work: On the Problem of Decomposing a Graph into n Connected Factors
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Network reliability analysis: Part I
description: scientific article; zbMATH DE number 4074786