A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees
Abstract
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.
Cite
Text
Becker and Geiger. "A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees." Conference on Uncertainty in Artificial Intelligence, 1996.Markdown
[Becker and Geiger. "A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees." Conference on Uncertainty in Artificial Intelligence, 1996.](https://mlanthology.org/uai/1996/becker1996uai-sufficiently/)BibTeX
@inproceedings{becker1996uai-sufficiently,
title = {{A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees}},
author = {Becker, Ann and Geiger, Dan},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {1996},
pages = {81-89},
url = {https://mlanthology.org/uai/1996/becker1996uai-sufficiently/}
}