An Inclusion-Exclusion Algorithm for Network Reliability with Minimal Cutsets

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+m3+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.

Share and Cite:

Y. Sun and W. Zhou, "An Inclusion-Exclusion Algorithm for Network Reliability with Minimal Cutsets," American Journal of Computational Mathematics, Vol. 2 No. 4, 2012, pp. 316-320. doi: 10.4236/ajcm.2012.24043.

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

Journals Menu
Follow SCIRP
Contact us
customer@scirp.org
WhatsApp +86 18163351462(WhatsApp)
Click here to send a message to me 1655362766
Paper Publishing WeChat

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.