An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed Networks

This paper studies the problem of computing the source-to-terminal reliability, the probability that a source s can communicate with a terminal t, in a probabilistic directed network. It introduces a set of reliability-preserving reductions, called 2-neighbor-node reductions. We show that for a class of directed networks, called BSP-digraphs, such reductions are always admissible and the source-to-terminal reliability can be computed in time linear in the size of the network. A directed network D = (V, E) is a BSP-digraph if its underlying undirected graph is series-parallel. The BSP-digraphs considered can be cyclic or acyclic and both vertices as well as edges can fail. Any two vertices can be chosen as s and t. Previously, no polynomial time algorithms were known for this class of digraphs. The proposed method is also applicable to mixed graphs containing directed and undirected edges.