Graph Decompositions and Algorithmic Applications


Lecture in Winter Term 2018/2019



Mon, 16:30 - 18:00 Uhr (5054)
Thu, 12:30 - 14:00 Uhr (5056)

Exercise Class
Tue, 12:30 - 14:00 Uhr (5054)



Decompositions of graphs serve as a useful tool in the design of efficient algorithms in many application domains ranging from combinatorial optimisation to probabilistic inference in artificial intelligence. Decompositions - and also indecomposability - may also help us to understand the structure of graphs and networks.

This course is an introduction to connectivity and decompositions of graphs and other structures. There is an elegant mathematical framework, built around a so-called connectivity systems, for studying connectivity. At the core of the theory is a duality between decompositions and highly connected regions, which can be described by objects known as tangles.

A particular focus of the course will be on algorithmic aspects. We will see efficient algorithms for computing decompositions as well as algorithms which exploit decompositions to solve other problems. In fact, we will see general algorithmic techniques known as dynamic programming and divide-and-conquer for doing this.


This course is addressed to students of the masters course, who have a clear interest in theoretical computer science.



The lecture will be held in English.


Martin Grohe


There are oral exams. The exact modalities of the exams are announced in L2P.


External Links