Logic and
Theory of
Discrete Systems

Informatik 7

 

Graph Decompositions and Algorithmic Applications

Introduction

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 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.

 

Lectures

Time and Place

Tuesday, 12:15 - 13:45 in 2356|050 (AH V)

Thursday, 13:15 - 14:45 in 2356|055 (5055)

(This 3-hour course will be held as 4-hour course, but not every week. The exact dates will be announced in the first lecture on 25.10.2016)

 Lecturer

Martin Grohe

 

Tutorials

Monday, 10:15 - 11:45 in 2356|055 (5055) held by Patrick Landwehr

The first tutorial will be on 07.11.2016.

 

Exams

The exact modalities will be announced later.