Factoring Algorithms for Computing K-Terminal Network Reliability

Let GK denote a graph G whose edges can fail and with a set K ¿ V specified. Edge failures are independent and have known probabilities. The K-terminal reliability of GK, R(GK), is the probability that all vertices in K are connected by working edges. A factoring algorithm for computing network reliability recursively applies the formula R(GK) = piR(GK * ei) + qiR(GK - ei) where GK * ei is GK, with edge ei contracted, GK - ei is GK with ei deleted and pi ¿ 1 - qi is the reliability of edge ei. Various reliability-preserving reductions can be performed after each factoring operation in order to reduce computation. A unified framework is provided for complexity analysis and for determining optimal factoring strategies. Recent results are reviewed and extended within this framework.