The week's pick
Random Articles
Reseach Article
Cutset Enumerating and Network Reliability Computing by a new Recursive Algorithm and Inclusion Exclusion Principle
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 45 - Number 16 |
| Year of Publication: 2012 |
| Authors: Mohamed Benaddy, Mohamed Wakrim |
10.5120/6864-9403
|
Mohamed Benaddy, Mohamed Wakrim . Cutset Enumerating and Network Reliability Computing by a new Recursive Algorithm and Inclusion Exclusion Principle. International Journal of Computer Applications. 45, 16 ( May 2012), 22-25. DOI=10.5120/6864-9403
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.
Index Terms
Keywords