IEEE Transactions on Reliability · 2007 · 199 citations · 23 references
ComputingComputer EngineeringComputer ScienceComputer NetworksFault-tolerant ComputingFault-tolerant SystemsBoolean Network ModelsNetwork ReliabilityReliability ModelingReliable System DesignBinary Decision DiagramsBoolean FunctionsElectric Power NetworksK-terminal ReliabilityNetwork DecompositionNetwork Reliability AlgorithmsNode FailuresRandom Failures
We present a network decomposition method using binary decision diagrams (BDD), a state-of-the-art data structure to encode, and manipulate Boolean functions, for computing the reliability of networks such as computer, communication, or power networks. We consider the K-terminal reliability measure R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</sub> , which is defined as the probability that a subset K of nodes can communicate with each other, taking into account the possible failures of the network links. We present an exact algorithm for computing the if-terminal reliability of a network with perfect vertices in O(m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">.</sup> F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">.</sup> 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Fmax.</sup> B <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Fmax</sub> ), where B <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Fmax</sub> is the Bell number of the maximum boundary set of vertices F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</sub> , and m is the number of network links. Several examples, and experiments show the effectiveness of this approach.
23
Akers · IEEE Transactions on Computers · 1978 · 1.8K citations
Network reliability and the factoring theorem
A. Satyanarayana, Mark K. Chang · Networks · 1983 · 253 citations