Computational Investigations of All-Terminal Network Reliability via BDDs

Hiroshi IMAI  Kyoko SEKINE  Keiko IMAI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.5   pp.714-721
Publication Date: 1999/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
network reliability,  BDD,  output-size sensitive,  #P-complete,  

Full Text: PDF>>
Buy this Article



Summary: 
This paper reports computational results of a new approach of analyzing network reliability against probabilistic link failures. This problem is hard to solve exactly when it is large-scale, which is shown from complexity theory, but the approach enables us to analyze networks of moderate size, as demonstrated by our experimental results. Furthermore, this approach yields a polynomial-time algorithm for complete graphs, whose reliability provides a natural upper bound for simple networks, and also leads to an efficient algorithm for computing the dominant part of the reliability function when the failure probability is sufficiently small. Computational results for these cases are also reported. This approach thus establishes a fundamental technology of analyzing network reliability in practice.