For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computational Investigations of All-Terminal Network Reliability via BDDs
Hiroshi IMAI Kyoko SEKINE Keiko IMAI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/05/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
network reliability, BDD, output-size sensitive, #P-complete,
Full Text: PDF(586.3KB)>>
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.