Title |
Branch and Bound algorithms for treewidth: Moplex vertices and/or Clique Switching |

Student |
Vacancy |

Supervisor |
Hans Bodlaender |

ECTS |
7.5 or 15 |

Related Course(s) |
Algorithms and Networks |

Description |
In this project, algorithms are studied to compute the treewidth of a given graph exactly,
with help of a branch and bound algorithm.
We build upon earlier Experimentation Projects. We use the LibTW framework
(a library with several algorithms to compute or approximate the treewidth), The branch and bound algorithm computes the treewidth, by looking for a permutation of
the vertices with minimum "width". In this project, we will test one or both of the following new, and yet untried techniques to speed up branch and bound algorithms for treewidth: - "clique switching": while constructing the permutation, edges are added, and new cliques appear.
It may be sometimes advantageous to change the clique at the end to a larger one. - selecting only "moplex" vertices: graph theory tells us that we only have to branch on vertices
that fulfill a certain property called "moplex".
This property can be tested with a modification of the depth first search algorithm.
we could test for moplex vertices only at the first levels of the branch and bound search. The LibTW library is written in Java, and thus this project also will be done in Java. |

Special Note |