A note on bounding \(k\)-terminal reliability (Q1186804): Difference between revisions

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.