A Fast Recursive Algorithm to Calculate the Reliability of a Communication Network

This paper describes a recursive algorithm to calculate the probability that all paths between two nodes in a given network are interrupted. It is assumed that all links are undirected and that links and nodes fail with given probabilities. These failures are assumed to be statistically independent. The probability that two nodes are disconnected is expressed in terms of the probability that pairs of nodes are disconnected in subnetworks smaller than the original one. The advantage of the algorithm given in this paper compared to other known procedures results from the fact that, in most cases, these subnetworks can be considerably simplified. These simplifications lead to considerable savings in computing time.