Graph Decompositions and Algorithmic Applications

 

Lecture in Winter Term 2018/2019

 

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

Martin Grohe

Exam

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