A Polynomial Time Algorithm for Computing Reliability of Two Classes of Networks
计算两类网络的可靠性的多项式时间算法

In this paper, two classes of directed networksORCnetworks and IRCnetworks are defined, and a polynomial time algorithm is presented for computing their rooted communication reliability, i.e. the probability that a specified vertex, root vertex, can communicate with all other vertices. The complexity of the algorithm for ORCnetworks and IRCnetworks is O(|E|) and O(|V||E|) respectively, where |V| and |E| are the number of vertices and of edges of networks respectively.