  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.
