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

Avinash Agrawal and A. Satyanarayana
Additional contact information
Avinash Agrawal: University of California, Berkeley, California
A. Satyanarayana: University of California, Berkeley, California

Operations Research, 1984, vol. 32, issue 3, 493-515

Abstract: 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.

Keywords: 432 network reliability algorithm; 488 and 721 network reliability (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.3.493 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:3:p:493-515

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().