[Dept. of Computer Science]

Experimentation Project ACS


Title Exact Algorithms for the Independent Set Problem
Student Ludo Stroetenga
Supervisor Hans Bodlaender
ECTS 7.5
Related Course(s) Algorithms and Networks
Description In this project, algorithms that find maximum independent sets in graphs, using the branch and reduce approach will be studied.
Recent theoretical developments, in particular the measure and conquer technique, make it possible to give much more precise
theoretical worst-case estimates on the running times of this type of algorithms.
In the project, we will study running times, as appearing in an experimental setting.
Different variants of branch and reduce algorithms for independent set will be studied, such that the effect of several reduction
rules or branching strategies can be investigated.
Special Note