Optimierungsprobleme auf Graphen sind in Theorie und Praxis allgegenwärtig. Häufig bietet sich für große Graphen eine Zerlegung in Probleme auf Teilgraphen an, um das Gesamtproblem nach dem Teile-und-herrsche-Prinzip zu lösen. Dabei kann zum einen nur der Graph als solches zerlegt werden, zum anderen eröffnen sich auch neue algorithmische Perspektiven. In diesem Seminar behandeln wir sowohl theoretische Ansätze zur Graphzerlegung als auch konkrete zerlegungsbasierte Lösungsmethoden für kombinatorische Optimierungsprobleme.

Insbesondere betrachten wir:
- Graphpartitionierung bzw. balancierte Schnitte
- Baum- und Branchzerlegungen

Das Seminar wird als Blockseminar durchgeführt.

- Themenvergabe: Mittwoch, 16.10., 10 Uhr c.t., ZIB, Seminarraum 2006
- Kick-off: tba
- Blockseminar: tba

Beim zweiten Treffen (Kick-off) sollen die Studenten einen Kurzvortrag (max. 5 Minuten) über ihr Thema halten.

Die Vorträge am Tag des Blockseminars sollen eine Dauer von 45 Minuten haben. Zur erfolgreichen Teilnahme gehört außerdem die Anfertigung einer schriftlichen Ausarbeitung der wesentlichen Inhalte in professioneller Qualität (LaTeX, 5-8 Seiten).

Voraussetzungen: Grundlagen der Graphentheorie, etwa im Umfang von Diskrete Mathematik I

Ergänzend empfiehlt sich fakultativ auch der Besuch der Vorlesungen Optimierung I (Ralf Borndörfer) oder Optimale Touren in Graphen (Niels Lindner).