Algorithms and Experiments for Finding Weighted
under the guidance of Dan
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
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.