An Algorithm for Network Reliability Bounds

We provide a new algorithm for assessing network reliability (and performability, the more general case). As in some well-known approaches, the algorithm identifies most probable states in iterations and provides converging upper and lower bounds after each iteration. The algorithm distinguishes itself by providing superior bounds after the same number of iterations. In some instances, the algorithm can even find the exact reliability in a small number of iterations. The time complexity for each iteration, excluding the time for computing the performance value of a generated state, is only O(n) (where n is the number of components), which is the same as any existing optimal algorithm for enumerating most probable states.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.