Abstract

In this work we present a new and efficient recursive algorithm that enumerate all the s-t minimal cut sets (MCs) separating nodes s (source) and t (terminal) in a network system. The networks studied here are considered as the undirected graphs. Later enumerating all the MCs, the inclusion-exclusion principle is used to compute the network reliability based on the probabilities of the links

References

• Chang, Y. -R. , Lin, H. -Y. , Chen, I. -Y. & Kuo, S. -Y. , A Cut-Based Algorithm for Reliability Analysis of Terminal-Pair Network Using OBDD, Proceedings of the 27th Annual International Conference on Computer Software and Applications, 2003.
• Fard, N. S. & Lee, T. -H. , Cutset enumeration of network systems with link and node failures, Reliability Engineering and System Safety 1999, pp. 141 - 146.
• JGraphT, http://jgrapht. org/
• Khachiyan, L. , Boros, E. , Elbassioni, K. , Gurvich, V. & Makino, K. , Enumerating disjunctions and conjunctions of paths and cuts in reliability theory, Discrete Appl. Math 2007, pp. 137-149.
• Lin, H. -Y. , Kuo, S. -Y. & Yeh, F. -M. , Minimal Cutset Enumeration and Network Reliability Evaluation by Recursive Merge and BDD, in ISCC '03: Proceedings of the 8th IEEE international Symposium on Computers and Communications, 2003, pp. 1341-1346.
• Shier, D. R. & Whited, D. E. , Algorithms for Generating Minimal Cutsets by Inversion, Reliability, IEEE Transactions vol R-34, 1985, pp. 314 -319.
• Tan, Z. , Minimal cut sets of s–t networks with k-out-of-n nodes, Reliability Engineering & System Safety 2003, pp. 49 - 54.
• Tsukiyama, S. , Shirakawa, I. , Ozaki, H. & Ariyoshi, H. , An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset, J. ACM 27 1980, pp. 619-632.
• Yeh, W. -C. , A simple algorithm for evaluating the k-out-of-n network reliability, Reliability Engineering and System Safety 2004, pp. 93 - 101.
• Yeh, W. -C. , A new algorithm for generating minimal cut sets in k-out-of-n networks, Reliability Engineering and System Safety 2006, pp. 36 - 43.