计算网络两终端可靠度的新分解算法  

New decomposition algorithm for computing two-terminal network reliability

作　　者：牛义锋[1] 王艳红[1] 徐秀珍[2] 

机构地区：[1]河南理工大学数学与信息科学学院,河南焦作454000 [2]河南理工大学计算机科学与技术学院,河南焦作454000

出　　处：《计算机工程与应用》2011年第30期79-82,89,共5页Computer Engineering and Applications

基　　金：河南理工大学青年基金(No.Q2009-31;No.Q2010-35)

摘　　要：网络可靠度是衡量网络性能的一个核心指标,随着网络模型被广泛应用于现实生活,人们对网络可靠度的研究也越来越重视。针对不交和算法和因子分解算法在计算网络可靠度方面存在的不足,给出一个计算网络两终端可靠度的新分解算法。该算法具有如下的优点:不需要提前枚举网络的所有极小路和所有极小割;通过引入网络化简操作和新的分解技术。该算法每次可以分解多条边的状态,从而它能够更快速、更高效地去分解网络的状态向量集,使得网络可靠度的计算更简单,更高效。通过实例以及和其他算法的比较验证了所提出算法的正确性和有效性。Network reliability is a core index of network performance evaluation.With the extensive application of network models in realistic life,people take more attentions on the research of network reliability.Considering the shortcomings of sum-of-disjoint products algorithm and factoring decomposition algorithm,a new decomposition algorithm for computing two-terminal network reliability is proposed.The proposed algorithm has the following advantages：It doesn’t require all MPs and all MCs to be enumerated in advance;By introducing the network simplification operations and a novel decomposition technique,the proposed algorithm can decompose the state of more edges each time,so it can decompose the state vectors set of the network more quickly and more effectively.Therefore,computing reliability becomes simpler,and more efficient.Finally,the correctness and efficiency of the proposed algorithm are illustrated by an example and comparisons with other algorithms.

关 键 词：网络可靠度 极小路 极小割 状态向量 分解技术 

分 类 号：TN913.2[电子电信—通信与信息系统]