A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees
arXiv:1302.3558
Abstract
An algorithm is developed for finding a close to optimal junction tree of a given graph G. The algorithm has a worst case complexity O(c^k n^a) where a and c are constants, n is the number of vertices, and k is the size of the largest clique in a junction 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 optimal value. When k = O(log n), our algorithm yields a polynomial inference algorithm for Bayesian networks.
Appears in Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence (UAI1996)
Cited by in corpus (5)
- Efficient Approximation for Triangulation of Minimum Treewidth
- A Variational Approximation for Bayesian Networks with Discrete and Continuous Latent Variables
- Computational Advantages of Relevance Reasoning in Bayesian Belief Networks
- Pre-processing for Triangulation of Probabilistic Networks
- Topological Parameters for Time-Space Tradeoff