A new analysis technique for probabilistic graphs

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.