A DECOMPOSITION ALGORITHM FOR NETWORK RELIABILITY EVALUATION

This paper presents an algorithm for computing the K-terminal reliabil ity of undirected networks, i.e. the probability that a given set of v ertices in the network are connected, when edges and nodes fail indepe ndently with known probabilities. This algorithm is based on a decompo sition method introduced by Rosenthal. It consists in numbering the ve rtices of the graph so that the successive boundary sets are as small as possible and in evaluating the probabilities of appropriate classes of boundary sets. We show that for the all terminal reliability probl em these classes are the partitions of the boundary sets and we descri be them for the general problem. Our computational results are so conc lusive that networks much larger than those presented before can now b e treated.