Algorithms to determine the threshold reliability of flow networks

The threshold reliability Rd of a flow network G can be defined in terms of the flow threshold d as the probability that network G admits a flow of at least d from the source node to the sink node. A fast exact algorithm to evaluate the threshold reliability of flow networks in terms of a sum of disjoint products is presented. In the proposed algorithm, a reliability product can be derived under a branching product in O(m) time using a d-path where m is the number of arcs in the network. Two algorithms are also presented to approximate the threshold reliability by modifying the proposed exact algorithm so that it can be terminated faster but at the cost of a lower accuracy. One is obtained by setting an acceptable difference value between the upper and lower bounds of the threshold reliability as the stopping criterion of the exact algorithm and the other is obtained by searching qualified α–products. Since the threshold reliability problem is NP-hard, approximation algorithms are indispensable for solving moderate and large flow networks. The proposed exact algorithm is verified using experimental data and the performances and properties of the two approximation algorithms are also explored and compared.