Wintersemester 2013/14
Thema: Das Max-Flow-Problem
In jüngerer Zeit (zuletzt 2013) gab es einige Fortschritte bei diesem klassischen Problem. In diesem Seminar werden anpruchsvolle Originalarbeiten behandelt, die weit über den Stoff von Lehrbüchern hinausgehen.
| Nr. | Probevortrag 12 Uhr c.t. |
Vortrag 14 Uhr c.t. |
Name | Thema | Betreuung |
|---|---|---|---|---|---|
| 1 | 14.10. | 28.10. | Doris Benda | A data structure for dynamic trees | Daniel Rotter |
| 2 | 21.10. | 4.11. | Simon Omlor | Approximating s-t minimum cuts in Õ(n2) time | Jan Schneider |
| 3 | 28.10. | 11.11. | Bento Natura | A faster deterministic maximum flow algorithm (I) | Philipp Ochsendorf |
| 4 | 4.11. | 18.11. | Lukas Miething | A faster deterministic maximum flow algorithm (II) | Philipp Ochsendorf |
| 5 | 11.11. | 25.11. | Andreas Haupt | Beyond the flow decomposition barrier | Jan Schneider |
| 6 | 18.11. | 2.12. | Jakob Nussbaumer | Max flows in O(nm) time, or better | Michael Gester |
| 7 | 25.11. | 9.12. | Alexander Platz | Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs (I) | Ulrike Suhl |
| 8 | 2.12. | 16.12. | Lukas Dreyer | Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs (II) | Ulrike Suhl |
| 9 | 9.12. | Wird am 27.1.2014 nachgeholt | Alexander Göke | A new approach to computing maximum flows using electrical flows | Niko Klewinghaus |
| 10 | 16.12. | 13.1. | Judith Brecklinghaus | Navigating central path with electrical flows: from flows to matching, and back (I) | Rudolf Scheifele |
| 11 | 6.1. | 20.1. | Steffen Böhmer | Navigating central path with electrical flows: from flows to matching, and back (II) | Rudolf Scheifele |
Eine Liste der Artikel, die den Vorträgen zugrundeliegen, findet sich hier.
- Von allen Teilnehmerinnen und Teilnehmern werden eine regelmäßige Teilnahme und eine aktive Mitarbeit erwartet.
- Die Vorträge sollen höchstens 75 Minuten dauern. Anschließend sind dann 15 Minuten für eine Diskussion vorgesehen.
- Alle Teilnehmerinnen und Teilnehmer müssen eine Zusammenfassung ihres Vortrags anfertigen, die mindestens eine und höchstens zwei Seiten lang ist.
- Alle Teilnehmerinnen und Teilnehmer müssen außerdem einen Probevortrag halten, der zwei bis drei Wochen vor dem eigentlichen Vortrag stattfindet. Ein erfolgreicher Probevortrag ist Voraussetzung für den Vortrag im Seminar.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner