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

摘要

This paper is concerned with the problem of computing the source-to-terminal reliability, the probability that a source s can send communication to a terminal t, in a probabilistic directed network. A set of reliability-preserving reductions, called 2-neighbor node reductions is introduced. It is shown 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. 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. No polynomial time algorithms were known previously for this class of digraphs. The proposed method is also applicable to mixed graphs containing directed and undirected edges.