Algorithms and Experiments for Finding Weighted Treewidth

under the guidance of  Dan Geiger

by Nickolay Dovgolevsky


Experimenting with real data using new and known algorithms to produce a practical state-of-the-art vertex elimination algorithm for usage in various applications including Bayesian networks, genetic linkage analysis, and combinatorial problems.


1. Using reduction rules as preprocessing. Main conclusion is a set of good reductions that are worthy to apply in almost every problem.

2. Comparison of stochastic greedy algorithms. Main conclusion is that a stochastic weighted fill-in algorithm due to Dan Geiger is the best so far.

3. Experiments on eight known benchmarks. Main conclusion is that the weighted fill-in algorithm is comparative to simulated annealing in reaching close to optimal cost but is much faster.


The problem of finding treewidth has been the subject of research for many years.