Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees
Ann Becker, Dan Geiger
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.
Keywords:
Pages: 81-89
PS Link:
PDF Link: /papers/96/p81-becker.pdf
BibTex:
@INPROCEEDINGS{Becker96,
AUTHOR = "Ann Becker and Dan Geiger",
TITLE = "A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees",
BOOKTITLE = "Proceedings of the Twelfth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-96)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1996",
PAGES = "81--89"
}


hosted by DSL   •   site info   •   help