|Title||Local search algorithms for treewidth|
|ECTS||7.5 or 15|
|Related Course(s)||Algorithms and Networks|
|Description||In this project, algorithms are studied to compute the treewidth of a given graph approximately,
with help of algorithms of "local search type", e.g., simulated annealing or Tabu Search.
We use the LibTW framework, a library with several algorithms to compute or approximate
the treewidth which was made in an earlier experimentation project,
This project aims to extend the framework with heuristic algorithms for treewidth that use
In a paper "Heuristic and Meta-Heuristic Methods for Computing Graph Treewidth" by Clautiaux et al.
(2004), a tabu search algorithm for treewidth was described.
In this project, we will experiment with this/and or variants of this method.