Many hard optimization problems from different fields of research are modeled by use of networks/graphs. Frequently, the underlying network structure of these problems can be characterized by a sparsity that allows for decompositions with relatively small treewidth. Such decompositions can very often be used to solve the optimization problem for quite large instances, that are not feasibly solvable by standard techniques that do not exploit a decomposition of the underlying network structure.

This project aims at two targets. First, we want to be able to efficiently and effectively find good tree decompositions of graphs. In the literature this issue has mainly been treated from a theoretical viewpoint. Our main objective is to develop techniques which generate good or even optimal tree decompositions for a wide variety of graphs. Second, we want to study the use of good tree decompositions for solving hard combinatorial optimization problems, modeled on graphs, as has been done for the frequency assignment problem.

• Utrecht University, The Netherlands : Hans Bodlaender
• University Maastricht, The Netherlands : Stan van Hoesel, Alexander Grigoriev, Bert Marchal
• Texas A & M University, USA: Illya V. Hicks