东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2010, Vol. 31 ›› Issue (4): 486-489.DOI: -

• 论著 • 上一篇    下一篇

计算有圈有向网络根通信可靠度的因子分解算法

孙艳蕊;毕继国;张祥德;   

  1. 东北大学理学院;辽宁省人民医院计算中心;
  • 收稿日期:2013-06-20 修回日期:2013-06-20 出版日期:2010-04-15 发布日期:2013-06-20
  • 通讯作者: -
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(60475036)

Computing rooted communication reliability of cyclic directed networks using the factoring method

Sun, Yan-Rui (1); Bi, Ji-Guo (2); Zhang, Xiang-De (1)   

  1. (1) School of Sciences, Northeastern University, Shenyang 110004, China; (2) Computing Center, The People's Hospital of Liaoning Province, Shenyang 110052, China
  • Received:2013-06-20 Revised:2013-06-20 Online:2010-04-15 Published:2013-06-20
  • Contact: Sun, Y.-R.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

671

摘要： 对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是O(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.

关键词: 根通信可靠度, 因子分解公式, 有圈有向网络, 可靠度保持缩减

Abstract: A reliability-preserving reduction and an factoring edge-selection strategy are presented by using the topological structure of cyclic directed network. Then, an efficient factoring algorithm is developed to compute the rooted communication reliability of cyclic directed networks. The time complexity of the algorithm is O(N·(|V|+|E|)), where N is the total number of the nodes as leaves on the binary tree originated from the algorithm, and |V| and |E| are the numbers of nodes and edges in a network, respectively. With some networks computed by the algorithm, it is found that the value of N resulting from computing the rooted communication reliability is much less than that resulting from other algorithms, thus verifying the higher effectiveness of the algorithm proposed.

中图分类号: