A Practical Algorithm for Finding Optimal Triangulations.
AAAI'97/IAAI'97: Proceedings of the fourteenth national conference on artificial intelligence and ninth conference on Innovative applications of artificial intelligence（1997）
摘要
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.
更多查看译文
关键词
clique tree inference algorithm,maximal clique,maximum clique,optimal triangulation,Bayesian inference,constraint satisfaction problem,reasonable time frame,triangulate graph,undirected graph,optimal triangulations,practical algorithm
AI 理解论文
溯源树
样例
生成溯源树，研究论文发展脉络
Chat Paper
正在生成论文摘要