✦ LIBER ✦

Edge-packing of graphs and network reliability

✍ Scribed by Charles J. Colbourn

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 842 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90193-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 edgepacking spanning trees, s, t-paths, and s, t-cuts to the determination of reliability bounds. The application of spanning trees has been studied by Polesskii, and the application of s, t-paths has been studied by Brecht and Colbourn. 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.

📜 SIMILAR VOLUMES

Packing k-edge trees in graphs of restri

Packing k-edge trees in graphs of restricted vertex degrees

✍ A.K. Kelmans 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

## Abstract Let ${\cal G}^{s}\_{r}$ denote the set of graphs with each vertex of degree at least __r__ and at most __s__, __v__(__G__) the number of vertices, and τ~__k__~ (__G__) the maximum number of disjoint __k__‐edge trees in __G__. In this paper we show that if __G__ ∈ ${\cal G}^{s}\_{2}$ a

Optimally reliable graphs for both edge

Optimally reliable graphs for both edge and vertex failures

✍ Trefor Evans; Derek Smith 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 331 KB

Graph theoretic characterization and rel

Graph theoretic characterization and reliability of the multiple-clique network

✍ Wen-Shyong Hsieh; Chu-Sing Yang; Jih-Shaw Tzeng 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 648 KB

Combinatorial properties of directed gra

Combinatorial properties of directed graphs useful in computing network reliability

✍ A. Satyanarayana; Jane N. Hagstrom 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 455 KB

On unreliability polynomials and graph c

On unreliability polynomials and graph connectivity in reliable network synthesis

✍ F. T. Boesch 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 607 KB

Orthogonal Decomposition and Packing of

Orthogonal Decomposition and Packing of Complete Graphs

✍ Yair Caro; Raphael Yuster 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 165 KB

An H-decomposition of a graph G is a partition of the edge-set of G into subsets, where each subset induces a copy of the graph H. A k-orthogonal H-decomposition of a graph G is a set of k H-decompositions of G, such that any two copies of H in distinct H-decompositions intersect in at most one edge