Computing the SKT Reliability of Acyclic Directed Networks Using Factoring Method  

作　　者：孔繁甲 王光兴 

机构地区：[1]DepartmentofComputerScience,NortheasternUniversity,Shengang110006,P,R.China [2]DepartmentofComputerScien

出　　处：《Journal of Computer Science & Technology》1999年第1期56-63,共8页计算机科学技术学报（英文版）

摘　　要：This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-networks) in which both nodes and edges can fail. Based on Pivotal decomposition theorem, a new formula is derived for computing the SKT reliability of AD-networks. By establishing a topological property of AD-networks, it is shown that the SKT reliability of AD- networks can be computed by recursively applying this formula. Two new Reliability- Preserving Reductions are also introduced. The recursion tree generated by the presented algorithm has at most 2 leaf nodes, where V and K are the numbers of nodes and terminals, respectively, while C is the number of the nodes satisfying some specified conditions. The computation complexity of the new algorithm is O (E. V. 2) in the worst case, where E is the number of edges. For source-to-all-terminal (SAT) reliability, its computation complexity is O(E). Comparison of the new algorithm with the existing ones indicates that the new algorithm is more efficient for computing the SKT reliability of AD-networks.This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-networks) in which both nodes and edges can fail. Based on Pivotal decomposition theorem, a new formula is derived for computing the SKT reliability of AD-networks. By establishing a topological property of AD-networks, it is shown that the SKT reliability of AD- networks can be computed by recursively applying this formula. Two new Reliability- Preserving Reductions are also introduced. The recursion tree generated by the presented algorithm has at most 2 leaf nodes, where V and K are the numbers of nodes and terminals, respectively, while C is the number of the nodes satisfying some specified conditions. The computation complexity of the new algorithm is O (E. V. 2) in the worst case, where E is the number of edges. For source-to-all-terminal (SAT) reliability, its computation complexity is O(E). Comparison of the new algorithm with the existing ones indicates that the new algorithm is more efficient for computing the SKT reliability of AD-networks.

关 键 词：network reliability acyclic directed network factoring algorithm reliability-preserving reduction 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]