Reliability Computations for Planar Networks

The two-terminal reliability problem for an undirected network involves calculating the probability that two distinguished sites are connected by a path of working edges. This problem is known to be NP-hard, even for the special case of planar systems. We present efficient data structures and algorithms for manipulating planar networks and for generating both paths an cutsets in such networks. A pseudopolynomial algorithm is then implemented, based on these generation procedures, to calculate two-terminal reliability for planar networks; that is, the algorithm's time complexity is polynomially bounded in the number of paths (or the number of cutsets). Computational experience with this implementation is also presented, showing that it provides a substantial improvement over previous implementations of the pseudopolynomial algorithm.

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