A Matrix Decomposition Algorithm for Enumerating All Minimal Cut-set of a Network

doi:10.13190/jbupt.200702.123.yuld

JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM ›› 2007, Vol. 30 ›› Issue (2): 123-126.doi: 10.13190/jbupt.200702.123.yuld

• Reports • Previous Articles Next Articles

A Matrix Decomposition Algorithm for Enumerating All Minimal Cut-set of a Network

YU Liang-de, SUN Xin-li, PENG Ya-hui

(103 Department,The Second Artillery Engineering College, xi’an 710025, China)

Received:2006-04-20 Revised:1900-01-01 Online:2007-04-30 Published:2007-04-30
Contact: YU Liang-de

Abstract

Abstract:

The definition of adjacent matrix was extended in order to effectively enumerate all minimal cut-set of a terminal network. And a matrix decomposition algorithm was then proposed. The algorithm is based on recursive matrix decomposition and reduction. The theoretical rationale and operational rules are given. The judgment principles and reduction rules about redundant nodes and isomorphic graphs are presented. The examples given show correctness and applicability of the algorithm.

Key words: network reliability, minimal cut-set, adjacent matrix

CLC Number:

TP202.1

YU Liang-de, SUN Xin-li, PENG Ya-hui
. A Matrix Decomposition Algorithm for Enumerating All Minimal Cut-set of a Network[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2007, 30(2): 123-126.

References

[1] Chang Yung-Ruei, Lin Hung-Yan, Chen Ing-Yi. A cut based algorithm for reliability analysis of terminal pair network using OBDD //Proceedings of the 27th Annual International Computer Software and Application Conference. Washington: IEEE Computer Society, 2003: 368-373.
[2] 孙新利, 陆长捷. 工程可靠性教程[M]. 北京: 国防工业出版社, 2005: 49-58. Sun Xinli, Lu Changjie. Reliability engineering [M]. Beijing: National Defense Industrial Press, 2005: 49-58.
[3] Lin Hung-Yau, Kuo Sy-Yen, Yeh Fu-Min. Minimal cut-set enumeration and network reliability evaluation by recursive merge and BDD //Proceedings of the Eighth IEEE International Symposium on Computers and Communication (ISCC'03). Washington: IEEE Computer Society, 2003: 1341-1346.
[4] Shier D R, Whited D E. Iterative algorithms for genera-ting minimal cut-set in directed graphs [J]. Networks, 1986, 16(4): 133-147.
[5] Lin J Y, Donaghey C E. A Monte Carlo simulation to determine minimal cut sets and system reliability //Proceedings Annual Reliability and Maintainability Symposium. Houston: Univ of Houston, 1993: 246-250.
[6] 武小悦. 复杂关联系统的可靠性建模与分析. 长沙: 国防科学技术大学信息系统与管理学院, 2000. Wu Xiaoyue. Reliability modeling and analysis of complex correlative system . Changsha: School of Information System & Management, National Univ of Defense Technology, 2000.
[7] Shier D R. Network reliability and algebraic structure [M]. Oxford: Clarendon Press, 1991: 62-71.
[8] Behr A, Camarinopoulos L, Pampoukis G. Domination of k-out-of-n systems[J]. IEEE Transaction on Reliabi-lity, 1995, 44(4): 705-707.
[9] Martelli H. A Gaussian elimination algorithm for the enumeration of cut sets in a graph[J]. Journal of ACM, 1976, 23(3): 58-73.
[10] Tsukiyama S, Shirakawa I, Ozaki H, et al. An algorithm to enumerate all cut-set of a graph in linear time per cut[J]. Journal of the ACM,1980, 27(4): 619-632.

A Matrix Decomposition Algorithm for Enumerating All Minimal Cut-set of a Network

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	XING Ning-zhe, ZHANG Si-dong, LI Zhi-ling. Path Optimization Method in Power Communication Network Based on Particle Swarm Optimization [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2016, 39(s1): 59-62.
[2]	WANG Li-qian,CHEN Xue,MA Dong-chao. Analysis on Modeling of PON Networks Reliability [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(5): 66-70.
[3]	ZHANG Xue-yuan, ZHANG Jing, LIANG Xiong-jian, Villy B.Iversen. Network Outage and Measurement in Telecommunications Network [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2001, 24(1): 17-21.