Comparing loop cutsets and clique trees in probabilistic inference
Linda C. van der Gaag, Hans L. Bodlaender · 1997
More and more knowledge-based systems are being developed that employ the framework of Bayesian belief networks for reasoning with uncertainty. Such systems generally use for probabilistic inference either the algorithm of J. Pearl or the algorithm of S.L. Lauritzen and D.J. Spiegelhalter. These algorithms build on different graphical structures for their underlying computational architecture. By comparing these structures we examine the complexity properties of the two algorithms and show that Lauritzen and Spiegelhalter's algorithm has at most the same computational complexity as Pearl's algorithm.