A New Algorithm for the Reliability Analysis of Multi-Terminal Networks

In a probabilistic network, source-to-multiple-terminal reliability (SMT reliability) is the probability that a specified vertex can reach every other vertex. This paper derives a new topological formula for the SMT reliability of probabilistic networks. The formula generates only non-cancelling terms. The non-cancelling terms in the reliability expression correspond one-to-one with the acyclic t-subgraphs of the network. An acyclic t-subgraph is an acyclic graph in which every link is in at least one spanning rooted tree of the graph. The sign to be associated with each term is easily computed by counting the vertices and links in the corresponding subgraph. Overall reliability is the probability that every vertex can reach every other vertex in the network. For an undirected network, it is shown the SMT reliability is equal to the overall reliability. The formula is general and applies to networks containing directed or undirected links. Furthermore link failures in the network can be s-dependent. An algorithm is presented for generating all acyclic t-subgraphs and computing the reliability of the network. The reliability expression is obtained in symbolic factored form.