Computing Network Reliability

This paper presents an algorithm to compute reliability measures on a stochastic network in which both nodes and links can fail. The measures considered are the probability that nodes s and t can communicate for all node pairs s and t, the probability that all operative node pairs can communicate, and the expected number of node pairs communicating. It also computes the latter two measures when all communication must proceed through a root node. A specialized version of the algorithm is given for networks in which only nodes can fail.