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 |

Description |
In this project, we look at exact (exponential time) algorithms that solve
the Dominating Set problem on graphs. 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 |