Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

VL Graph Decompositions

Lecturer: Dr. Steffen van Bergerem


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.


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


Thursday, 13:00-15:00 (bi-weekly), Erwin-Schrödinger-Zentrum (RUD26), room 1'307