[Dept. of Computer Science]

Experimentation Project ACS

Title Local search algorithms for pathwidth
Student Vacancy
Supervisor Hans Bodlaender
ECTS 7.5, possibly extendible to 15
Related Course(s) Algorithms and Networks

In this project, algorithms are studied to compute the pathwidth of a given graph approximately, with help of algorithms of "local search type",
e.g., simulated annealing or Tabu Search.

The algorithm builds upon an earlier project, where such algorithms were investigated for the related notion of treewidth.

Pathwidth has several applications, e.g., recently Hans Bodlaender received an email of a researcher in robotics that looked for pathwidth algorithms,
as pathwidth represents a form of "graph search".

We use the LibTW framework, a library with several algorithms to compute or approximate the treewidth which was made in an earlier experimentation project,
and also succesfully used and extended in other experimentation projects.

In this project, we will experiment with this/and or variants of this method. Depending on time, a number of the following questions will be investigated:

  • how does tabu search compare to simulated annealing (or other similar methods) using the same cost functions and neighborhood structures?
  • what settings give best results?

The project can be done in Java with the LibTW framework, or in another programming language.

Special Note