Improving the Kuo-Lu-Yeh Algorithm for Assessing Two-Terminal Reliability

Currently, the most efficient approach for solving the NP-hard terminal-pair reliability problem is the Kuo-Lu-Yeh algorithm which applies the technique of Edge Expansion Diagram (EED) coupled with Ordered Binary Decision Diagram (OBDD). In this work we will show that this algorithm can be enhanced significantly by removing redundant biconnected components, which can be done in linear time and without needing additional memory. We empirically evaluated our approach against the original one by means of 24 benchmark networks. In addition, we examined our approach statistically using randomly generated graphs. Our new approach performs significantly better regarding runtime and memory consumption for most of the benchmark networks. For a regular 3x20 grid network we have even achieved a speedup of 464 and the memory consumption goes down to 0.3 percent. Thus, in practice, runtime and memory consumptions are drastically reduced for many "difficult" networks. When applied to networks without redundant biconnected components, there is no memory overhead and the additional runtime is negligible.