Premium
Triconnected decomposition for computing K ‐terminal network reliability
Author(s) -
Wood R. Kevin
Publication year - 1989
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.3230190203
Subject(s) - combinatorics , factoring , undirected graph , reliability (semiconductor) , mathematics , constant (computer programming) , terminal (telecommunication) , discrete mathematics , decomposition , enhanced data rates for gsm evolution , graph , algorithm , computer science , physics , telecommunications , power (physics) , ecology , finance , quantum mechanics , economics , biology , programming language
Abstract Let R ( G k ) denote the probability that a subset of vertices K in the undirected graph G = ( V, E ) can communicate when the edge of G fail independently with known probabilities. Suppose that G k contains as separting pair of vertices { u , v } such that G k = G̃ k̃ ∪ Ǧ ǩ , Ṽ ∩ V̂ ={u v}, Ẽ ∩ Ê = ø, |Ẽ| ⩾ 2, and |Ê| ⩾2. It is shown that Ĝ k may be replaced by a chain χ of at most three edges between u and v such that R ( G k ) = ΩR ((G̃ ∪ χ) k̃′ ) where Ω is a derived constant and K̃′ is defined by the procedure. The failure probabilities of the edges in χ and the value of Ω are shown to be computable by evaluating the reliability of one of four variants of Ĝ k̂ . Minimal components Ĝ k̂ can be efficiently found using triconnected decomposition and the above procedure embedded within a recursive factoring algorithm for computing K ‐terminal reliability. Conditions are derived which guarantee the new algorithm is at least as good as a pure factoring algorithm, and an example shows that the new algorithm can be exponentially better.