Graph Decompositions and Algorithmic Applications
Lecture in Summer Term 2022
Content
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.
Prerequisites
This course is addressed to students of the masters course, who have a clear interest in theoretical computer science.
Organization
The lecture will be held in English.
Lecturer