Wintersemester 2005/06
Thema: Kürzeste Wege
Termin: montags 14-16 Uhr
In diesem Seminar werden anhand von Originalarbeiten fortgeschrittene Algorithmen zur Berechnung kürzester Wege in Netzwerken vorgestellt, die deutlich über die klassischen Verfahren (Dijkstra-Algorithmus, Moore-Bellman-Ford-Algorithmus) hinausgehen.
| Nr. | Datum | Name | Thema | Betreuung |
|---|---|---|---|---|
| 1 | 24.10. | Daniela Stollenwerk | R.K. Ahuja, K. Mehlhorn, J.B. Orlin und R.E. Tarjan, Faster algorithms for the shortest path problem, J. Assoc. Comput. Mach. 37, (1990) | Jürgen Werber |
| 2 | 31.10. | Jan Schneider | M.L. Fredman und D.E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, J. Comput. Syst. Sci. 48, (1994) | Ulrich Brenner |
| 3 | 7.11. fällt aus! | Azzam Hajdaoud | M. Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, J. Comput. Syst. Sci. 69, (2004) bzw. STOC '03 | Sven Peyer |
| 4 | 14.11. | Manuel Peelen / Mario Boley | M. Thorup, Undirected single-source shortest paths with positive integer weights in linear time, J. ACM 46, (1999) (I) | Dirk Müller |
| 5 | 21.11. | Manuel Peelen / Mario Boley | M. Thorup, Undirected single-source shortest paths with positive integer weights in linear time, J. ACM 46, (1999) (II) | Dirk Müller |
| 7 | 5.12. | Daniel Dressler | T. Hagerup, Simpler Computation of Single-Source Shortest Paths in Linear Average Time, STACS 2004, LNCS 2996, und Teile von A.V. Goldberg, A simple shortest path algorithm with linear average time, ESA 2001, LNCS 2161, und U. Meyer, Single-source shortest-paths on arbitrary directed graphs in linear average-case time, SODA 2001 |
Jens Maßberg |
| 8 | 12.12. | Christian Oppel | M.L. Fredman, New bounds on the complexity of the shortest path problem, SIAM J. Comput. 5 (1976), und R. Seidel, On the All-Pairs-Shortest-Path Problem, STOC '92 |
Markus Struzyna |
| 9 | 19.12. fällt aus! | Folie Astadiko | T. Takaoka, Subcubic cost algorithms for the all pairs shortest path problem, Algorithmica 20, (1998) | Markus Struzyna |
| 10 | 16.1. | Christian Schulte | U. Zwick, A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths, ISAAC 2004, LNCS 3341 | Christian Panten |
| 11 | 23.1. | Friedemann Koepke | N. Young, R. Tarjan und J. Orlin, Faster Parametric Shortest Path and Minimum Balance Algorithms, Networks 21 (1991) | Stephan Held |
| 6 | 30.1 (verschoben vom 28.11.) | Krisztian Simon | A.V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM J. Comput. 24, 494-504 (1995) | Stephan Held |
Voraussetzungen:
Vordiplom und mindestens eine Vorlesung (besser mehrere) aus dem Bereich der Diskreten Mathematik oder Mathematischen Optimierung.Wichtig: Die Kenntnis von Kapitel 7 aus dem Buch
B. Korte, J. Vygen : Combinatorial Optimization: Theory and Algorithms, Springer, Zweite Auflage 2002
wird ebenfalls vorausgesetzt. Ab September wird auch die dritte Auflage des oben angegebenen Buches verfügbar sein.
Scheinkriterien:
erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive MitarbeitProf. Dr. B. Korte,
Prof. Dr. D. Rautenbach,
Prof. Dr. J. Vygen