Calculating K-connectedness reliability using Steiner bounds

Calculating K-connectedness reliability using Steiner bounds

0.00 Avg rating0 Votes
Article ID: iaor20041133
Country: United States
Volume: 21
Issue: 4
Start Page Number: 905
End Page Number: 921
Publication Date: Nov 1996
Journal: Mathematics of Operations Research
Authors: ,
Abstract:

The K-connectedness reliability problem considered in this paper has as input undirected graph G, subset K of terminal vertices, and common edge failure probability p, and as output the probability R(G, K, p) that – when edges fail independently each with probability p – the set of operating edges connect every pair of vertices of K. We show how the Steiner property held by the underlying simplicial complex associated with this problem can lead to an extension of the Ball–Provan shellability bounds to this more general problem. We show in computational studies that this bound performs quite favorably in comparison with known approximation techniques.

Reviews

Required fields are marked *. Your email address will not be published.