VL Graph Decompositions
Lecturer: Dr. Steffen van Bergerem
Contents
Many computationally hard problems become tractable if the underlying structure of a problem instance is simple. For example, most graph problems are easily solvable if the graph is a tree. Hence, graph decompositions that decompose graphs into simpler structures are a useful tool for the design of efficient algorithms. This course gives an introduction to decompositions of graphs and other structures. In particular, we consider tree decompositions, which will be the central notion for most of the course. In addition to characterisations of such decompositions via combinatorial games, we also study algorithmic consequences, including powerful algorithmic meta-theorems.
Lecture
Monday, 11:00-13:00, Erwin-Schrödinger-Zentrum (RUD26), room 1'306
Thursday, 13:00-15:00 (bi-weekly), Erwin-Schrödinger-Zentrum (RUD26), room 1'307
Exercise
Thursday, 13:00-15:00 (bi-weekly), Erwin-Schrödinger-Zentrum (RUD26), room 1'307