The Delta-Wye Approximation Procedure for Two-Terminal Reliability

The Delta-Wye Approximation Procedure (DWAP) is a procedure for estimating the two-terminal reliability of an undirected planar network G = (V, E) by reducing the network to a single edge via a sequence of local graph transformations. It combines the probability equations of Lehman—whose solutions provide bounds and approximations of two-terminal reliability for the individual transformations—with the Delta-Wye Reduction Algorithm of the second two authors—which performs the corresponding graph reduction in O(|V|²) time. A computational study is made comparing the DWAP to one of the best currently known methods for approximating two-terminal reliability, and it is shown that the DWAP produces approximations that are between 10 and 80 times as accurate.