A Unified Formula for Analysis of Some Network Reliability Problems

A topological formula is derived for solving a variety of network reliability problems such as vertex-to-vertex communication from a source to a terminal; from a source to some specified subset of the vertices or else all vertices; between any given vertex-pair; between all vertex-pairs within a given subset of the vertices; or else between all vertex-pairs. The formula applies to networks consisting of imperfect (unreliable) vertices and/or links, and with failure events s-independent or not. The formula explicitly characterizes the structure of both cancelling and noncancelling terms in the reliability expression obtained by Inclusion-Exclusion, and involves only noncancelling terms. Earlier topological formulas for the source-to-terminal problem and the source-to-all-vertices problem are shown to be special cases of this new one.