[Dept. of Computer Science]

Experimentation Project ACS

Title A New Lowerbound for Treewidth
Student Vacancy
Supervisor Hans Bodlaender
ECTS 7.5, possibly extendible to 15
Related Course(s) Algorithms and Networks
Description

In a recent paper, a new graph parameter is defined, in terms of a "graph search game".
(Richerby and Thilikos, Searching for a visible, lazy fugitive, to appear in Proceedings Workshop on Graph Theoretic Concepts in Computer Science 2008)

The authors also give a polynomial time algorithm to compute the parameter for given graphs, and show that the parameter is a lower bound for treewidth.

In this project, this algorithm will be implemented and evaluated. Questions are:

  • how fast is this algorithm? How does it compare to other
  • results in the literature for treewidth lower bounds?
The project can be done in Java with the LibTW framework, or in another programming language.
Special Note