Abstract:In this paper, two classes of directed networks——ORC-networks and IRC-networks 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 ORC-networks and IRC-networks is O(|E|) and O(|V|·|E|) respectively, where |V| and |E| are the number of vertices and of edges of networks respectively.