Title |
Computing Treewidth |

Students |
Thomas van Dijk, Wouter Slob, Jan-Pieter van den Heuvel |

Supervisor |
Hans Bodlaender |

ECTS |
15 per student |

Related Course(s) |
Algorithms and Networks |

Description |
For several purposes, it is often useful to compute the treewidth
of a graph, or to find a tree decomposition with small treewidth. Results can for example be applied to probabilistic networks and combinatorial optimization problems. In this project several algorithms for computing the treewidth of graphs are evaluated: - Exact algorithms for computing treewidth, e.g. branch-and-bound algoriths, dynamic programming algorithms;
- Algorithms that provide upper bounds (heuristics for computing treewidth; the minimum degree algorithm, the minimum fill-in algorithm, and variants);
- Algorithms for finding lower bounds.
The different algorithms are compared on quality
(how good are the solutions compared to optimality), and on their
time and possibly memory requirements. |