Terminal reliability in a communication network: an efficient algorithm

The terminal reliability between two nodes defined as the probability of existence of least one path between these nodes. The nodes are assumed perfectly reliable, while to each arc assigned an independent probability of existence. The problem of computing the terminal reliability is a tough combinatorial problem. Existing methods compute and evaluate a symbolic expression, which either is the sum of the independent probabilities of a large number of elementary disjoint events, or is the expansion, using the inclusion-exclusion principle, of the probabilities of a relatively small number of correlated events. The algorithm presented in this paper uses Boolean algebra simplification techniques and computes a symbolic expression which is the sum of probabilities of disjoint non-elementary events. Thus , this expression is much simpler. Further- more a computer implementation gives evidence that this algorithm can solve ever shown in the literature. For even larger graphs, an approximate algorithm, which gives symbolic expression for lower and upper bounds of the terminal reliability, is also described and implemented.