A sum of disjoint products algorithm for reliability evaluation of flow networks

This paper proposes a revised algorithm to evaluate the unreliability of a flow network in which capacities of arcs are assumed to be independent binary-valued random variables. Such a problem is a generalization of the well-known NP-hard two-terminal reliability problem which evaluates the probability of the connection from a source node to a sink node. The proposed algorithm is motivated by Rueger. Both in a branching manner, the proposed and Rueger's algorithms express the system unreliability in terms of a sum of disjoint products where each product is derived from a branching condition B via a d-cutB in O(m·log m) time and via the first system failure under B in O(d·n²·2^m) time respectively where d is the demand, n and m are the numbers of nodes and arcs in the network respectively. Experimental experiences show that the proposed algorithm drastically reduces the execution time and performs more robustly, when compared to Rueger's algorithm, but the number of disjoint products derived by it will be a little bit larger.