Abstract :
1. The three algorithms, inclusion-exclusion (IE), sum of disjoint products (SDP), and topological reliability (TR), all have the exponential-time property; this means that it cannot be guaranteed that a large problem can be solved in polynomial time, but that it might be possible to do so in special cases. 2. IE or SDP results in a system reliability formula which is a sum of products of the probabilities of the components; unlike IE, with SDP the terms of the formula are disjoint. Experimental results show that with large systems, SDP results in a shorter formula than IE. 3. In the special case of an m-out-of-n system, by ordering the paths so that each path differs from its predecessor by exactly one component, the SDP probability formula has the same number of terms as there are paths, and the formula is derived and solved in polynomial time. 4. Certain proofs are provided for SDP: a. the inner and outer loops of the Abraham algorithm. b. counting of computer operations for m-out-of-n systems. 5. The direct relationship between the IE and TR formulas is described. With IE, the formula is a sum of terms, where each term is the product of component reliabilities, whereas the TR formula is in nested and factored form. 6. This paper revises the explanation of TR given in the seminal 1978 paper by Satyanarayana & Prabhaker, while retaining the terminology anad procedures proposed by S&P 7.
