Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Efficient Approximation for Triangulation of Minimum Treewidth
Eyal Amir
Abstract:
We present four novel approximation algorithms for finding triangulation of minimum treewidth. Two of the algorithms improve on the running times of algorithms by Robertson and Seymour, and Becker and Geiger that approximate the optimum by factors of 4 and 3 2/3, respectively. A third algorithm is faster than those but gives an approximation factor of 4 1/2. The last algorithm is yet faster, producing factor-O(lg/k) approximations in polynomial time. Finding triangulations of minimum treewidth for graphs is central to many problems in computer science. Real-world problems in artificial intelligence, VLSI design and databases are efficiently solvable if we have an efficient approximation algorithm for them. We report on experimental results confirming the effectiveness of our algorithms for large graphs associated with real-world problems.
Keywords:
Pages: 7-15
PS Link:
PDF Link: /papers/01/p7-amir.pdf
BibTex:
@INPROCEEDINGS{Amir01,
AUTHOR = "Eyal Amir ",
TITLE = "Efficient Approximation for Triangulation of Minimum Treewidth",
BOOKTITLE = "Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2001",
PAGES = "7--15"
}


hosted by DSL   •   site info   •   help