Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481570 | European Journal of Operational Research | 2009 | 15 Pages |
With increasing emphases on better and more reliable services, network systems have incorporated reliability analysis as an integral part in their planning, design and operation. This article first presents a simple exact decomposition algorithm for computing the NP-hard two-terminal reliability, which measures the probability of successful communication from specified source node to sink node in the network. Then a practical bounding algorithm, which is indispensable for large networks, is presented by modifying the exact algorithm for obtaining sequential lower and upper bounds on two-terminal reliability. Based on randomly generated large networks, computational experiments are conducted to compare the proposed algorithm to the well-known and widely used edge-packing approximation model and to explore the performance of the proposed bounding algorithm. Computational results reveal that the proposed bounding algorithm is superior to the edge-packing model, and the trade-off of accuracy for execution time ensures that an exact difference between upper and lower bounds on two-terminal reliability can be obtained within an acceptable time.