计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (30): 79-82.

• 网络、通信、安全 • 上一篇    下一篇

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

牛义锋1,王艳红1,徐秀珍2   

  1. 1.河南理工大学 数学与信息科学学院,河南 焦作 454000
    2.河南理工大学 计算机科学与技术学院,河南 焦作 454000
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-10-21 发布日期:2011-10-21

New decomposition algorithm for computing two-terminal network reliability

NIU Yifeng1,WANG Yanhong1,XU Xiuzhen2   

  1. 1.School of Mathematics & Information Science,Henan Polytechnic University,Jiaozuo,Henan 454000,China
    2.School of Computer Science & Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-10-21 Published:2011-10-21

摘要: 网络可靠度是衡量网络性能的一个核心指标,随着网络模型被广泛应用于现实生活,人们对网络可靠度的研究也越来越重视。针对不交和算法和因子分解算法在计算网络可靠度方面存在的不足,给出一个计算网络两终端可靠度的新分解算法。该算法具有如下的优点:不需要提前枚举网络的所有极小路和所有极小割;通过引入网络化简操作和新的分解技术。该算法每次可以分解多条边的状态,从而它能够更快速、更高效地去分解网络的状态向量集,使得网络可靠度的计算更简单,更高效。通过实例以及和其他算法的比较验证了所提出算法的正确性和有效性。

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

Abstract: 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.

Key words: network reliability, minimal path, minimal cut, state vector, decomposition technique