Seminar on Combinatorial Optimization: Graph Decomposition
Akt: 25.10.2019 14:00
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
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).