A NEW FORMULA AND AN ALGORITHM FOR RELIABILITY-ANALYSIS OF NETWORKS

In 1978, Satyanarayana and Prabhakar (SP) proposed a new topological f ormula for the source-to-terminal (ST) reliability of complex networks . The formula generates only non-cancelling terms of the reliability e xpression which correspond one-to-one with the p-acyclic subgraphs of the given network. Based on the concept of neutral sequences in acycli c graphs, a powerful SP algorithm was presented for generating all p-a cyclic subgraphs and computing the ST reliability of the network. Comb ining an inclusion-exclusion algorithm with a sum of disjoint products algorithm, we introduce a new topological formula which includes the SP formulas as a special case. A new efficient algorithm which has all features of the SP algorithm is proposed. In general, the reliability expressions obtained by this algorithm are more compact than the ones obtained by the SP algorithm. Copyright (C) 1996 Elsevier Science Ltd .