All-Terminal Network Reliability Using Recursive Truncation Algorithm

Exact calculation of all-terminal network reliability is a hard problem; its computational complexity grows exponentially with the number of nodes and links in the network. We propose the Recursive Truncation Algorithm (RTA), a bounding approximation algorithm, to estimate the all-terminal reliability of a given network with a pre-specified accuracy. RTA scans all minimal cutsets of the graph representing the network, and finds the weak cutsets of the graph by comparing failure probabilities of cutsets to an adaptive threshold which depends on the approximation accuracy. We calculate the unreliability of the network versus the probabilities of occurrence of failure in the weak cutsets, and the probabilities of co-occurrence of failure in several weak cutsets, simultaneously. In addition to the all-terminal reliability, the RTA computes an upper, and a lower bound for the estimated reliability. We demonstrate that the estimated all-terminal reliability of a given network is within a pre-specified accuracy, and is more precise than those obtained by existing methods.