|Title||Preprocessing for Treewidth|
|Supervisor||Hans Bodlaender and Eelko Penninkx|
|ECTS||7.5 or 15|
|Related Course(s)||Algorithms and Networks|
|Description||Preprocessing is almost always a very useful technique when
we want to solve hard (e.g., NP-hard) problems.
The treewidth of graphs is a well studied notion and has several applications.
This experimentation project aims at implementing and comparing different
preprocessing methods for the problem to compute the treewidth of a given graph.
The project will concentrate on safe separator algorithms.
A separator is a set of vertices, that,
when removed from the graph, let the graph fall into several components.
The project will be done in Java and can be 7.5 or 15 "study points". See also the project on branch-and-bound algorithms for treewidth. It is possible to combine the projects.