| 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 |