|Title||Branch and Bound algorithms for treewidth: Moplex vertices and/or Clique Switching|
|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 exactly,
with help of a branch and bound algorithm.
We build upon earlier Experimentation Projects. We use the LibTW framework
(a library with several algorithms to compute or approximate the treewidth),
The branch and bound algorithm computes the treewidth, by looking for a permutation of
the vertices with minimum "width".
In this project, we will test one or both of the following new, and yet untried techniques to speed up branch and bound algorithms for treewidth:
we could test for moplex vertices only at the first levels of the branch and bound search.
The LibTW library is written in Java, and thus this project also will be done in Java.