Optimization problems on graphs are ubiquitous in theory and practice. Often it is reasonable to decompose large graphs into subgraphs in order to solve the problem following the divide-and-conquer principle. On the one hand, a graph may be decomposed itself, on the other, also several new algorithmic perspectives arise. In this seminar, we will cover theoretical approaches as well as practical decomposition-based solution methods for combinatorial optimization problems.

In particular, we will consider:
- Graph partitioning resp. balanced cuts
- Tree and branch decompositions

The seminar will be a block seminar.

- Assignment of topics: Wednesday, 16.10., 10 am, ZIB, seminar room 2006
- Kick-off: tba
- Block seminar: tba

At the second meeting (kick-off), students are expected to give a short presentation (max. 5 minutes) on their topic.
The talks on the day of the block seminar are supposed to take 45 minutes. For a successful participation, students need to hand in a written summary of the essential contents in professional quality (LaTeX, 5-8 pages).

Prerequisites: Basics of graph theory, e.g., Diskrete Mathematik I

As a complement, you may optionally visit the lectures Optimierung I (Ralf Borndörfer) or Optimale Touren in Graphen (Niels Lindner).