Comparing loop cutsets and clique trees in probabilistic networks

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 di erent 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 asPearl's algorithm.