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

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

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

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.