摘要
对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是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.
出处
《东北大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2010年第4期486-489,共4页
Journal of Northeastern University(Natural Science)
基金
国家自然科学基金资助项目(60475036)
关键词
根通信可靠度
因子分解公式
有圈有向网络
可靠度保持缩减
rooted communication reliability
factoring formula
cyclic directed network
reliability-preserving reduction
