A Practical Algorithm for Finding Optimal Triangulations
Abstract
An algorithm called QUICKTREE is developed for finding a triangulation T of a given undirected graph G such that the size of T’s maximal clique is minimum and such that no other triangulation of G is a subgraph of T. We have tested QUICKTREE on graphs of up to 100 nodes for which the maximum clique in an optimal triangulation is of size 11. This is the first algorithm that can optimally triangulate graphs of such size in a reasonable time frame. This algorithm is useful for constraint satisfaction problems and for Bayesian inference through the clique tree inference algorithm.
Cite
Text
Shoikhet and Geiger. "A Practical Algorithm for Finding Optimal Triangulations." AAAI Conference on Artificial Intelligence, 1997.Markdown
[Shoikhet and Geiger. "A Practical Algorithm for Finding Optimal Triangulations." AAAI Conference on Artificial Intelligence, 1997.](https://mlanthology.org/aaai/1997/shoikhet1997aaai-practical/)BibTeX
@inproceedings{shoikhet1997aaai-practical,
title = {{A Practical Algorithm for Finding Optimal Triangulations}},
author = {Shoikhet, Kirill and Geiger, Dan},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1997},
pages = {185-190},
url = {https://mlanthology.org/aaai/1997/shoikhet1997aaai-practical/}
}