Title :
A new analysis technique for probabilistic graphs
Author :
Dotson, William P. ; Gobien, Jurgen O.
fDate :
10/1/1979 12:00:00 AM
Abstract :
A new technique for determining the terminal reliability of probabilistic networks is derived and discussed. The technique uses set-theoretic concepts to partition the space of all graph realizations in a way which permits extremely fast evaluation of the source-to-terminal probability. If not allowed to run to completion, the algorithm yields rapidly converging upper and lower bounds on that probability. Comparison with algorithms in the recent literature shows a decrease of one or two orders of magnitude in required CPU time.
Keywords :
Communication networks; Communication system reliability; Graph theory; Graph theory and combinatorics; Network reliability; Stochastic networks; Central Processing Unit; Circuit theory; Circuits and systems; Communication system control; Electronic countermeasures; Graph theory; Partitioning algorithms; Reliability engineering; Telecommunication network reliability; Tree graphs;
Journal_Title :
Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCS.1979.1084573
