Hanging Edges for Fast Reliability Estimation

We show how to combine the hanging edges algorithm of Lomonosov with the cross-entropy (CE) and the splitting one in estimating the relia-bility of a large network in order to obtain a speed-up of order m / ln(m), where m is the number of edges in the network. The efficiency improve-ment is due to the fact that the reliability function of the network is evaluated via the proposed algorithm, instead of the conventional one. As a result, the standard cross-entropy and the standard splitting algorithms for network reliability can be accelerated by a factor of m / ln(m). We also present an enhanced splitting version based on hanging edges, which ensures a speed-up by a factor of m as compared to the basic splitting ver-sion. In addition, we show that combining the permutation Monte Carlo (PMC) algorithm of Elperin, Gertsbakh and Lomonosov with the hanging edges also provides a speed-up of orderm / ln(m) over the original PMC al-gorithm. We finally provide numerical evidence suggesting that the newl