A note on bounding k-terminal reliability

DOI10.1007/BF01758764MaRDI QIDQ1186804zbMATH OpenFDO

Authors Charles J. Colbourn

Publication date 28 June 1992

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01758764

zbMATH Keywords

\(k\)-terminal reliabilitygraph transformationreliability boundSteiner tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Reliability, availability, maintenance, inspection in operations research (90B25)

Review text

Given an undirected simple graph \(G=(V,E)\), in which each edge \(e\in E\) has probability \(p_ e\) of operation, and a set \(K\subseteq V\) (of cardinality \(k)\), a Steiner tree for \(K\) is an acyclic connected subgraph of \(G\) in which every vertex of degree 1 is in \(K\). The \(k\)-terminal reliability of \(G\) with respect to \(K\) is the probability that a subgraph of \(G\) formed by choosing each edge \(e\) with probability \(p_ e\) independently contains a Steiner tree for \(K\). There are several methods known for finding upper bounds for 2-terminal reliability [\textit{H. M. F. AboElFotoh} and \textit{C. T. Colbourn}, Series-parallel bounds for the two- terminal reliability problem, ORSA J. Comput. 1, 209-222 (1989)] and all- terminal reliability \((K=V)\) [\textit{M. O. Ball} and \textit{J. S. Provan}, Bounds on the reliability polynomial for shellable independence systems, SIAM J. Algebraic Discrete Methods 3, 166-181 (1982; Zbl 0504.05053)]. The paper under review presents a method for finding an upper bound for \(k\)-terminal reliability, using a graph transformation which reduces \(k\)- terminal reliability to all-terminal reliability.

Recommendations

• Calculating K-Connectedness Reliability Using Steiner Bounds
• Computing the \(K\)-terminal reliability of directed path graphs
• Efficient algorithms for computing the reliability of permutation and interval graphs
• scientific article; zbMATH DE number 21369
• On uniformly most reliable two-terminal graphs
• Reliability of communication networks with delay constraints: computational complexity and complete topologies
• Bounding network-reliability using consecutive minimal cutsets
• scientific article; zbMATH DE number 205333
• Triconnected decomposition for computingK-terminal network reliability

Cites work

• Bounds on the Reliability Polynomial for Shellable Independence Systems
• Edge-packings of graphs and network reliability
• scientific article; zbMATH DE number 3494439 (Why is no real title available?)
• scientific article; zbMATH DE number 3506434 (Why is no real title available?)
• Multi-Terminal Network Flows
• Reducibility among combinatorial problems
• Series-Parallel Bounds for the Two-Terminal Reliability Problem
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems

Cited in

(7)

• On the reliability bounds in k-HNBUE and k-HNWUE classes
• Generalized activities and \(K\)-terminal reliability
• Practical sequential bounds for approximating two-terminal reliability
• scientific article; zbMATH DE number 21369 (Why is no real title available?)
• Calculating K-Connectedness Reliability Using Steiner Bounds
• scientific article; zbMATH DE number 1161336 (Why is no real title available?)
• scientific article; zbMATH DE number 1490110 (Why is no real title available?)

This page was built for publication: A note on bounding \(k\)-terminal reliability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186804)