A sufficiently fast algorithm for finding close to optimal junction trees
Au algorithm is developed for findiug a close to optimal junction tree of a given graph G. The algorithm has a worst case complexity O(ckna) where a and c are constants, n is the nmnber of vertices, and k is the size of the largest clique in a juuction tree of G in which this size is minimized. The algorithm guarantees that the logarithm of the size of the state space of the heaviest clique in the junction tree produced is less than a constant factor off the optional value. When k = O(log n) our algorithm yields a polynomial inference algorithm for Bayesian networks.