[Dept. of Computer Science]

Experimentation Project ACS

Title Exact Algorithms for Dominating Set
Student Vacancy
Supervisor Hans Bodlaender/Johan van Rooij
ECTS 7.5 possibly extendible to 15
Related Course(s) Algorithms and Networks

In this project, we look at exact (exponential time) algorithms that solve the Dominating Set problem on graphs.
These algorithms typically have the following structure: branching steps are alternated with steps where simplification rules are applied.
There is much choice in how to branch, and when to apply what types of simplification.

Some existing algorithms that give provably good running times can be implemented, but in the project, also different choices can be investigated.

As some algorithms use a maximum matching algorithm, the project should be carried out in C++ using the Leda package, and preferably be done in the AlgoLab.

Special Note