Wintersemester 2007/08
Thema: Schnelle Matchingalgorithmen
Montags 14 Uhr c.t. im Seminarraum des Forschungsinstituts für Diskrete Mathematik, Lennéstr. 2. Die Probevorträge werden (mit Ausnahme des ersten Vortrags) montags um 16 Uhr c.t. gehalten.
Voraussetzungen:
Mindestens eine Vorlesung (besser mehrere) aus dem Bereich der Diskreten Mathematik oder Mathematischen Optimierung.| Nr. | Probevortrag | Vortrag | Name | Thema | Betreuung |
|---|---|---|---|---|---|
| 1 | 1.10. 14 Uhr c.t. |
15.10. | Matthias Schwamborn | Z. Galil, S. Micali, H. Gabow [1986]: An O(EV log V) algorithm for finding a maximal weighted matching in general graphs | Ulrich Brenner |
| 2 | 1.10. | 22.10. | Minglai Cai | R. Cole, K. Ost, S. Schirra [2001]: Edge-coloring bipartite multigraphs in O(E log D) time | Ulrich Brenner |
| 3 | 8.10. | 29.10. | Stefan Fritsch | T.C. Biedl, P. Bose, E.D. Demaine, A. Lubiw [2001]: Efficient algorithms for Petersen's matching theorem | Stephan Held |
| 4 | 15.10. | 5.11. | Elias Schäfer | R.J. Lipton, R.E. Tarjan [1979]: A separator theorem for planar graphs und R.J. Lipton, R.E. Tarjan [1980]: Applications of a planar separator theorem |
Stephan Held |
| 5 | 22.10. | 12.11. | Renate Holterhof | J.F. Geelen [2000]: An algebraic matching algorithm | Markus Struzyna |
| 6 | 29.10. | 19.11. | Laura Geisen | M. Mucha, P. Sankowski [2004]: Maximum matchings via Gaussian elimination | Markus Struzyna |
| 7 | 5.11. | 26.11. | Christoph Lauff | M. Mucha, P. Sankowski [2006]: Maximum matchings in planar graphs via Gaussian elimination | Markus Struzyna |
| 8 | 12.11. | 3.12. | Markus Moll | T. Feder, R. Motwani [1995]: Clique partitions, graph compression and speeding-up algorithms | Dirk Müller |
| 9 | 19.11. | 10.12. | Stephan Worm | D.E. Drake, S. Hougardy [2003]: A simple approximation algorithm for the weighted matching problem und S. Pettie, P. Sanders [2004]: A simpler linear time 2/3 - epsilon approximation for maximum weight matching, Abschnitt 3 |
Christian Schulte |
| 10 | 26.11. | 17.12. | Michael Otto | S. Pettie, P. Sanders [2004]: A simpler linear time 2/3 - epsilon approximation for maximum weight matching, Rest | Christian Schulte |
| 11 | 10.12. | 7.1. | Markus Mayer | K.R. Varadarajan [1998]: A divide-and-conquer algorithm for min-cost perfect matching in the plane | Jens Maßberg |
| 12 | 17.12. | 14.1. | Adrian Bock | T. Fischer, A.V. Goldberg, D.J. Haglin, S. Plotkin [1993]: Approximating matchings in parallel und R. Uehara, Z.-Z. Chen [2000]: Parallel approximation algorithms for maximum weighted matching in general graphs |
Christoph Bartoschek |
| 13 | 7.1. | 21.1. | Alexander von Dambrowski | S. Hougardy, D.E. Vinkemeier [2006]: Approximating weighted matchings in parallel | Christoph Bartoschek |
| 14 | 14.1. | 28.1. | Leonhard Schneider | M. Zelke [2006]: Optimal per-edge processing times in the semi-streaming model | Christian Schulte |
| 15 | 21.1. | 4.2. | Lena Haupt | A. McGregor [2005]: Finding graph matchings in data streams und J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, J. Zhang [2004]: On graph problems in a semi-streaming model |
Dirk Müller |
- Von allen Teilnehmerinnen und Teilnehmern werden eine regelmäßige Teilnahme und eine aktive Mitarbeit erwartet.
- Die Vorträge sollen etwa 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 in der Regel drei Wochen vor dem eigentlichen Vortrag statfindet. Ein erfolgreicher Probevortrag ist Voraussetzung für den Vortrag im Seminar
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Dr. U. Brenner