An algorithm for computing all-terminal reliability bounds

Abstract

The exact calculation of all-terminal reliability is not feasible in large networks. Hence estimation techniques and lower and upper bounds for all-terminal reliability have been utilized. We propose using an ordered subset of the mincuts and an ordered subset of minpaths to calculate an all-terminal reliability upper and lower bound, respectively. The advantage of the proposed approach results from the fact that it does not require the enumeration of all mincuts or all minpaths as required by other bounds. The performance of the algorithm is compared with the first two Bonferroni bounds, for networks where all mincuts could be calculated. The results show that the proposed approach is computationally feasible and reasonably accurate. Thus allowing one to obtain bounds when it not possible to enumerate all mincuts or all minpaths.