A recursive algorithm for finding reliability measures related to the connection of nodes in a graph

A recursive algorithm is developed for finding the probability that not all nodes are connected in a graph with arcs that can fail. The number of multiplications required by the algorithm when applied to a complete graph on n nodes is shown to be of order 3 n ‐1 , substantially less than other published algorithms. Further, it is shown that the algorithm enables other reliability measures related to the connection of nodes in a graph to be determined with minimal extra multiplications. The algorithm can also form the basis of methods for calculating the reliability measures of graphs with unreliable nodes and unreliable arcs. The complexity is then at worst 4 n and, in most cases, of order 3 n .