Computing the SKT Reliability of Acyclic Directed Networks Using Factoring Method

摘要

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~(|v|-|K|-|c|) leaf nodes, where |V| and |IK| 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|.|lV|. 2~(|v|-|k|-|c|)) 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.