Title |
Local search algorithms for pathwidth |

Student |
Vacancy |

Supervisor |
Hans Bodlaender |

ECTS |
7.5, possibly extendible to 15 |

Related Course(s) |
Algorithms and Networks |

Description |
In this project, algorithms are studied to compute the pathwidth of a given graph approximately,
with help of algorithms of "local search type", 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, We use the LibTW framework, a library with several algorithms to compute or approximate
the treewidth which was made in an earlier experimentation project, 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 |