Premium
A decomposition algorithm for network reliability analysis
Author(s) -
Shogan A. W.
Publication year - 1978
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230080307
Subject(s) - algorithm , partition (number theory) , computer science , computation , decomposition , network partition , partition problem , reliability (semiconductor) , path (computing) , decomposition method (queueing theory) , mathematics , discrete mathematics , distributed computing , combinatorics , computer network , ecology , power (physics) , physics , quantum mechanics , biology
Consider a directed, source‐sink network whose arcs either function or fail with known probabilities. This paper presents a decomposition algorithm for the exact computation of the reliability of such a network; that is, the probability that there exists a path from the network's source to its sink, consisting only of functioning arcs. The decomposition algorithm, which can be used even after the network can undergo no further modular decomposition, is based on a partitioning of the nodes of the network into subsets that can be sequentially analyzed. The algorithm permits arbitrary dependence among arcs that terminate at nodes belonging to the same subset of the partition but requires two arcs terminating at nodes belonging to different subsets to be independent. Computational experience from a computer implementation of the algorithm is also reported.