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

Computing Rooted Communication Reliability of Cyclic Directed Networks Using the Factoring Method

作　　者：孙艳蕊[1] 毕继国 张祥德[1] 

机构地区：[1]东北大学理学院,辽宁沈阳110004 [2]辽宁省人民医院计算中心,辽宁沈阳110052

出　　处：《东北大学学报（自然科学版）》2010年第4期486-489,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(60475036)

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

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

分 类 号：TP202.1[自动化与计算机技术—检测技术与自动化装置]