网络系统最小割集的一种矩阵分解

doi:10.13190/jbupt.200702.123.yuld

北京邮电大学学报 ›› 2007, Vol. 30 ›› Issue (2): 123-126.doi: 10.13190/jbupt.200702.123.yuld

网络系统最小割集的一种矩阵分解

余良德, 孙新利, 彭亚会

(第二炮兵工程学院 103教研室，西安 710025)

收稿日期:2006-04-20 修回日期:1900-01-01 出版日期:2007-04-30 发布日期:2007-04-30
通讯作者: 余良德

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

中图分类号:

TP202.1

余良德, 孙新利, 彭亚会. 网络系统最小割集的一种矩阵分解[J]. 北京邮电大学学报, 2007, 30(2): 123-126.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价