Forschungsinstitut für Diskrete Mathematik

Hauptseminar Diskrete Optimierung

Wintersemester 2008/09

Thema: Algorithmen für kürzeste-Wege-Probleme

Montags 14 Uhr c.t. im Seminarraum des Forschungsinstituts für Diskrete Mathematik, Lennéstr. 2. Die Probevorträge werden montags um 16 Uhr c.t. gehalten.
Das Problem, kürzeste Verbindungen in einem Netzwerk zu finden, spielt in vielen wichtigen Anwendungen eine Rolle, z.B. bei der Routenplanung in Navigationssystemen oder beim Entwurf von höchstintegrierten Chips. In diesem Seminar werden effiziente Verfahren zur Lösung solcher Probleme vorgestellt. Wir betrachten sowohl das Problem, in einem Graphen von einer Quelle kürzeste Verbindungen zu einer gegebenen Menge von Knoten zu suchen, als auch das Problem, zwischen je zwei Knoten einen kürzesten Weg zu bestimmen. In jüngster Zeit hat es in diesem Bereich viele neue Ideen gegeben, und ein Großteil der Verfahren, die in diesem Seminar vorgestellt werden, stammt aus den vergangenen drei Jahren.
Nr. Probe-
vortrag		 Vortrag Name Thema Betreuung
1 29.9. 13.10.
Der Vortrag fällt aus. 		Marouan Bendib Kaplan, Tarjan [2008]: Thin heaps, thick heaps Christoph Bartoschek
2 6.10. 20.10. Benedikt Holl Ahuja, Mehlhorn, Orlin, Tarjan [1990]: Faster algorithms for the shortest path problem Christoph Bartoschek
3 13.10. 27.10. Sandro Grieger Goldberg [1995]: Scaling algorithms for the shortest paths problem Christoph Bartoschek
4 20.10. 10.11. Christopher Ohm Fakcharoenphol, Rao [2006]: Planar graphs, negative weight edges, shortest paths, and near linear time Dirk Müller
5 27.10. 17.11. Lars Bellinghausen Hagerup [2006]: Simpler computation of single-source shortest paths in linear average time
Goldberg [2008]: A practical shortest path algorithm with linear expected time 		Dirk Müller
6 10.11. 24.11. Tobias Schneider Hershberger, Maxel, Suri [2007]: Finding the k shortest simple paths: a new algorithm and its implementation
Yen [1971]: Finding the k shortest loopless paths in a network 		Markus Struzyna
7 17.11. 1.12. Alexander Timmermeister Fredman [1976]: New bounds on the complexity of the shortest path problem
Zwick [2006]: A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths 		Christian Schulte
8 24.11. 8.12. Daniel Joachimi Chan [2007]: More algorithms for all-pairs shortest paths in weighted graphs Markus Struzyna
9 1.12. 15.12. Torsten Stelljes Pettie [2004]: A new approach to all-pairs shortest paths on real-weighted graphs I Jens Maßberg
10 8.12. 22.12. Ivailo Manolov Pettie [2004]: A new approach to all-pairs shortest paths on real-weighted graphs II Jens Maßberg
11 15.12. 5.1. Maxim Janzen Saunders, Takaoka [2007] Solving shortest paths efficiently on nearly acyclic directed graphs Markus Struzyna
12 22.12. 12.1. Jan Zernisch Demetrescu, Italiano [2004]: A new approach to dynamic all pairs shortest paths Christian Schulte
13 5.1. 19.1.
Der Vortrag fällt aus. 		Shoshanna Seenberg Mehlhorn, Priebe [1997]: On the all-pair shortest-path algorithm of Moffat and Takaoka Ulrich Brenner
14 12.1. 26.1. Dmitri Mizerkin Sanders, Schultes [2005]: Highway hierarchies hasten exact shortest path queries
Sanders, Schultes [2007]: Engineering fast route planning algorithms
Goldberg, Kaplan, Werneck [2005]: Reach for A*: efficient point-to-point shortest path algorithms
Bauer, Delling [2008]: SHARC: fast and robust unidirectional routing 		Dirk Müller
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Dr. U. Brenner