On the complexity of computing tree-partitions
Time: 14:00 -- Location: LRI, 445
summary: Tree-partitions are graph decompositions that correspond to mapping vertices to nodes
of a tree in such a way that adjacent vertices in the graph are either mapped to adjacent nodes
of the tree or to the same node. The width of a tree-partition is the maximum number of vertices
mapped to a node. Many computational problems become tractable when given a tree-partition of
bounded width. This raises the question of computing such decompositions efficiently.
Joint work with Hans Bodlaender and Carla Groenland.