CALCULATING K-CONNECTEDNESS RELIABILITY USING STEINER BOUNDS

The K-connectedness reliability problem considered in this paper has a s input undirected graph G, subset K of terminal vertices, and common edge failure probability p, and as output the probability R(G, K, p) t hat-when edges fail independently each with probability p-the set of o perating edges connect every pair of vertices of K. We show how the St einer property held by the underlying simplicial complex associated wi th this problem can lead to an extension of the Ball-Provan shellabili ty bounds to this more general problem. We show in computational studi es that this bound performs quite favorably in comparison with known a pproximation techniques.