An Inclusion-Exclusion Algorithm for Network Reliability with Minimal Cutsets

Yan-Rui Sun, Wei-Yi Zhou

School of Electronic Information, Wuhan University, Wuhan, China.
School of Sciences, Northeastern University, Shenyang, China.

DOI: 10.4236/ajcm.2012.24043                

Abstract

The inclusion-exclusion formula (IEF) is a fundamental tool for evaluating network reliability with known minimal paths or minimal cuts. However, the formula contains many pairs of terms which cancel. Using the notion of comparable node partitions some properties of canceling terms in IEF are given. With these properties and the thought of “dynamic programming” method, a simple and efficient inclusion-exclusion algorithm for evaluating the source-to-terminal reliability of a network starting with cutsets is presented. The algorithm generates all the non-canceling terms in the unreliability expression. The computational complexity of the algorithm is O(n+m³+M), where n and m are the numbers of nodes and minimal cuts of the given network respectively, M is the number of terms in the final symbolic unreliability expression that generated using the presented algorithm. Examples are shown to illustrate the effectiveness of the algorithm.

Keywords

Inclusion-Exclusion Formula; Network Reliability; Minimal Cutset; Dynamic Programming

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	C. J. Colbourn, “The Combinatorics of Network Reliability,” Oxford University Press, New York Oxford, 1987.
[2]	M. O. Ball, C. J. Colbourn and J. S. Provan, “Network Reliability,” Handbook of Operations Research: Network Models, Elsevier North-Holland, Amsterdam, Vol. 7, 1995, pp. 673-762.
[3]	J. A. Buzacott, “Node Partition Formula for Directed Graph Reliability,” Networks, Vol. 17, No. 2, 1987, pp. 227-240. doi:10.1002/net.3230170207
[4]	J. A. Buzacott and S. K. Chang, “Cut Set Intersections and Node Partition,” IEEE Transactions on Reliability, Vol. 31, No. 4, 1982, pp. 385-389.
[5]	A. Satyanarayana and A. Prabhakar, “New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex Networks,” IEEE Transactions on Reliability, Vol. 27, No. 1, 1978, pp. 82-100. doi:10.1109/TR.1978.5220266
[6]	A. Satyanarayana and J. N. Hagstrom, “A New Algorithm for Reliability Analysis of Multi-Terminal Networks,” IEEE Transactions on Reliability, Vol. 30, No. 4, 1981, pp. 325-334. doi:10.1109/TR.1981.5221103
[7]	L. C. Zhao and F. J. Kong, “A New Formula and an Algorithm for Reliability Analysis of Network,” Microelectron Reliability, Vol. 37, No. 4, 1997, pp. 511-518.
[8]	W. C. Yeh, “A Greedy Branch-and-Bound Inclusion-Exclusion Algorithm for Calculating the Exact Multi-State Network Reliability,” IEEE Transactions on Reliability, Vol. 57, No. 1, 2008, pp. 88-93. doi:10.1109/TR.2008.916871