|Title||Branch and Bound Algorithms for Treewidth|
|Student||Ruud van den Beukel|
|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.
The treewidth of graphs is a well studied notion and has several applications. In this project, we build upon the LibTW framework
(a library with several algorithms to compute or approximate the treewidth) constructed in a previous experimentation project.
The project looks at an algorithm, proposed by Gogate and Dechter, and by
Bachoore and Bodlaender,
In this project, a number of techniques will be tried out to speed up such
branch and bound algorithms.