Publications
If you are new to the field of route planning, we recommend to read the most recent overview article.
Overview Articles
- Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner:
Engineering Route Planning Algorithms.
In: Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science. Springer, 2009.
to appear.
[ pdf ] - Dorothea Wagner and Thomas Willhalm:
Speed-Up Techniques for Shortest-Path Computations.
In: Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07), volume 4393 of Lecture Notes in Computer Science, pages 23-36. Springer, 2007.
[ pdf ]
PhD-Theses
- Daniel Delling:
Engineering and Augmenting Route Planning Algorithms.
PhD thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2009.
[ pdf ] - Martin Holzer:
Engineering Planar-Separator and Shortest-Path Algorithms.
PhD thesis, Universität Karlsruhe (TH), Fakultät Informatik, August 2008.
[ pdf ] - Thomas Willhalm:
Engineering Shortest Paths and Layout Algorithms for Large Graphs.
PhD thesis, Universität Karlsruhe (TH), Fakultät Informatik, 2005.
[ pdf ]
Time-Dependent Route Planning
- Veit Batz, Daniel Delling, Peter Sanders, and Christian Vetter:
Time-Dependent Contraction Hierarchies.
In: Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), pages 97-105. SIAM, 2009.
[ pdf ] - Daniel Delling and Giacomo Nannicini:
Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks.
In: Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC'08), volume 5369 of Lecture Notes in Computer Science, pages 813-824. Springer, December 2008.
[ pdf ] - Daniel Delling:
Time-Dependent SHARC-Routing.
In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA'08), volume 5193 of Lecture Notes in Computer Science, pages 332-343. Springer, September 2008.
Best Student Paper Award - ESA Track B.
[ pdf ] - Giacomo Nannicini, Daniel Delling, Leo Liberti, and Dominik Schultes:
Bidirectional A* Search for Time-Dependent Fast Paths.
In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 334-346. Springer, June 2008.
[ pdf ]
Multi-Criteria Shortest Paths
- Daniel Delling and Dorothea Wagner:
Pareto Paths with SHARC.
In: Proceedings of the 8th International Symposium on Experimental Algorithms (SEA'09), Lecture Notes in Computer Science. Springer, June 2009.
to appear.
[ pdf ]
Public Transportation
- Daniel Delling, Bastian Katz, and Thomas Pajor:
Parallel Computation of Best Connections in Public Transportation Networks.
In: 24th International Parallel and Distributed Processing Symposium (IPDPS'10). IEEE Computer Society, 2010.
accepted for publication, to appear. - Daniel Delling, Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis:
Efficient Route Planning in Flight Networks.
In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09), Dagstuhl Seminar Proceedings, 2009.
[ pdf ] - Daniel Delling, Thomas Pajor, and Dorothea Wagner:
Engineering Time-Expanded Graphs for Faster Timetable Information.
In: Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, September 2008.
[ pdf ] - Reinhard Bauer, Daniel Delling and Dorothea Wagner:
Experimental Study on Speed-Up Techniques for Timetable Information Systems.
Networks, 2009.
accepted for publication, to appear.
- Reinhard Bauer, Daniel Delling and Dorothea Wagner:
Experimental Study on Speed-Up Techniques for Timetable Information Systems.
In: Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07), pages 209-225. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2007.
[ html | pdf ] - Matthias Müller-Hannemann, Frank Schulz, Dorothea Wagner and Christos Zaroliagis:
Timetable Information: Models and Algorithms.
In: Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science, pages 67-90. Springer, 2007.
- Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis:
Efficient Models for Timetable Information in Public Transportation Systems.
ACM Journal of Experimental Algorithmics, 12:Article 2.4, 2007..
- Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis:
Experimental Comparison of Shortest Path Approaches for Timetable Information.
In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04), pages 88-99. SIAM, 2004.
[ pdf ] - Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis:
Towards Realistic Modeling of Time-Table Information through the Time-Dependent Approach.
In: Proceedings of ATMOS Workshop 2003, pages 85-103, 2004.
- Dorothea Wagner:
Algorithms and Models for Railway Optimization.
In: Algorithms and Data Structures, 8th International Workshop, volume 2748 of Lecture Notes in Computer Science, pages 198-206. Springer, 2003.
[ html ] - Frank Schulz, Dorothea Wagner, and Karsten Weihe:
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport.
ACM Journal of Experimental Algorithmics, 5, 2000.
- Frank Schulz, Dorothea Wagner, and Karsten Weihe:
Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport.
In: Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE'99), volume 1668 of Lecture Notes in Computer Science, pages 110-123. Springer, 1999.
[ html ]
Multi-Modal Route Planning
- Daniel Delling, Thomas Pajor, and Dorothea Wagner:
Accelerating Multi-Modal Route Planning by Access-Nodes.
In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09), volume 5757 of Lecture Notes in Computer Science, pages 587-598. Springer, September 2009.
[ pdf ] - Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav Marathe, and Dorothea Wagner:
Engineering Label-Constrained Shortest-Path Algorithms.
In: Proceedings of the Ninth DIMACS Implementation Challenge on Shortest Paths (DIMACS 2006). AMS, 2009.
To appear.
- Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav Marathe, and Dorothea Wagner:
Engineering Label-Constrained Shortest-Path Algorithms.
In: Proceedings of the Fourth International Conference on Algorithmic Aspects in Information and Management (AAIM 2008), volume 5034 of LNCS, pages 27-37. Springer, June 2008.
Theory
- Reinhard Bauer, Gianlorenzo D'Angelo, Daniel Delling, and Dorothea Wagner:
The Shortcut Problem - Complexity and Approximation.
In: Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'09), volume 5404 of Lecture Notes in Computer Science, pages 105-116. Springer, 2009.
[ pdf ] - Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner.
Preprocessing Speed-Up Techniques is Hard.
In: Proceedings of the 7th Conference on Algorithms and Complexity (CIAC'10), Lecture Notes in Computer Science. Springer, 2010.
Hierarchical Speed-Up Techniques
- Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling:
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.
In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 319-333. Springer, June 2008.
[ pdf ] - Daniel Delling, Martin Holzer, Kirill Müller, Frank Schulz, and Dorothea Wagner:
High-Performance Multi-Level Routing.
In: Shortest Paths: Ninth DIMACS Implementation Challenge, DIMACS Book. American Mathematical Society, 2009.
accepted for publication, to appear.
[ pdf ] - Martin Holzer, Frank Schulz and Dorothea Wagner:
Engineering Multi-Level Overlay Graphs for Shortest-Path Queries.
Journal of Experimental Algorithmics, 13, 2008.
© ACM 2007. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution.
[ pdf ] - Martin Holzer, Frank Schulz and Dorothea Wagner:
Engineering Multi-Level Overlay Graphs for Shortest-Path Queries.
In: Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX 2006), volume 129 of Proceedings in Applied Mathematics, pages 156-170. SIAM, January 2006.
[ pdf ] - Frank Schulz, Dorothea Wagner, and Christos Zaroliagis:
Using Multi-Level Graphs for Timetable Information in Railway Systems.
In: Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02), volume 2409 of Lecture Notes in Computer Science, pages 43-59. Springer, 2002.
[ pdf ]
Goal-Directed Speed-Up Techniques
- Edith Brunel, Daniel Delling, Andreas Gemsa and Dorothea Wagner:
Space-Efficient SHARC-Routing.
In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 47-58. Springer, May 2010.
- Reinhard Bauer and Daniel Delling:
SHARC: Fast and Robust Unidirectional Routing.
ACM Journal of Experimental Algorithmics, 2009.
Special issue devoted to ALENEX'08. To appear.
[ pdf ] - Reinhard Bauer and Daniel Delling:
SHARC: Fast and Robust Unidirectional Routing.
In: Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08), pages 13-26. SIAM, 2008.
[ pdf ] - Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm:
Partitioning Graphs to Speedup Dijkstra's Algorithm.
ACM Journal of Experimental Algorithmics, 11:2.8, 2006.
- Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, and Thomas Willhalm:
Partitioning Graphs to Speed Up Dijkstra's Algorithm.
In: Proceedings of the 4th Workshop on Experimental Algorithms (WEA'05), Lecture Notes in Computer Science, pages 189-202. Springer, 2005.
- Dorothea Wagner, Thomas Willhalm and Christos Zaroliagis:
Geometric Containers for Efficient Shortest-Path Computation.
ACM Journal of Experimental Algorithmics, 10:1.3, 2005.
- Dorothea Wagner, Thomas Willhalm and Christos Zaroliagis:
Dynamic Shortest Path Containers.
In: Proceedings of ATMOS Workshop 2003, pages 65-84, 2004.
[ pdf ] - Dorothea Wagner and Thomas Willhalm:
Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs.
In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA'03), volume 2832 of Lecture Notes in Computer Science, pages 776-787. Springer, 2003.
Combinations of Speed-Up Techniques
- Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner:
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm.
In: ACM Journal of Experimental Algorithmics, 15:2.3, January 2010.
- Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner:
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm.
In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 303-318. Springer, June 2008.
[ pdf ] - Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner:
Highway Hierarchies Star.
In: Shortest Paths: Ninth DIMACS Implementation Challenge, DIMACS Book. American Mathematical Society, 2009.
accepted for publication, to appear.
[ pdf ] - Martin Holzer, Frank Schulz, Thomas Willhalm and Dorothea Wagner:
Combining Speed-up Techniques for Shortest-Path Computations.
Journal of Experimental Algorithmics, 10, 2006.
© ACM 2006. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution.
[ pdf ] - Martin Holzer, Frank Schulz and Thomas Willhalm:
Combining Speed-up Techniques for Shortest-Path Computations.
In: Proceedings of the Third International Workshop on Experimental and Efficient Algorithms (WEA 2004), volume 3059 of LNCS, pages 269-284. Springer, May 2004.
[ pdf ]
Many-to-Many
- Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner:
Computing Many-to-Many Shortest Paths Using Highway Hierarchies.
In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07), pages 36-45. SIAM, 2007.
Master's Theses
- Thomas Pajor:
Multi-Modal Route Planning.
Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2009.
- Dennis Schieferdecker:
Systematic Combination of Speed-Up Techniques for exact Shortest-Path Queries.
Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2008.
- Sebastian Knopp:
Efficient Computation of Many-to-Many Shortest Paths.
Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2006.
- Reinhard Bauer:
Dynamic Speed-Up Techniques for Dijkstra's Algorithm.
Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2006.
[ pdf ] - Kirill Müller:
Design and Implementation of an Effcient Hierarchical Speed-up Technique for Computation of Exact Shortest Paths in Graphs.
Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2006.
- Martin Holzer:
Hierarchical Speed-up Techniques for Shortest-Path Algorithms.
Master's thesis, Dept. of Informatics, University of Konstanz, Germany, February 2003.
[ pdf ] - Frank Schulz:
Efficient Algorithms for a Timetable Information System.
Master's thesis, Dept. of Informatics, University of Konstanz, Germany, 2000.
Student Research Projects
- Edith Brunel:
Shortcut Removal on SHARC.
Student Research Project, Karlsruhe Institute of Technology (KIT), 2009. - Andreas Gemsa:
Arc-Flag Compression.
Student Research Project, Universität Karlsruhe (TH), Fakultät für Informatik, 2008.
- Thomas Pajor:
Goal Directed Speed-Up Techniques for Shortest-Path Queries in Timetable Networks.
Student Research Project, Universität Karlsruhe (TH), Fakultät für Informatik, 2008.
- Kirill Müller:
Berechnung kürzester Pfade unter Beachtung von Abbiegeverboten.
Student Research Project, Universität Karlsruhe (TH), Fakultät für Informatik, 2005.
- Sebastian Knopp:
Schnelle Berechnung von kürzesten Wegen in Graphen unter Benutzung höherdimensionaler Layouts.
Student Research Project, Universität Karlsruhe (TH), Fakultät für Informatik, 2005.
- Birk Schütz:
Partition-Based Speed-Up of Dijkstra s Algorithm.
Student Research Project, Universität Karlsruhe (TH), Fakultät für Informatik, 2005.
Related to Speed-Up Techniques
- Reinhard Bauer, Marcus Krug, Sascha Meinert, and Dorothea Wagner.
Synthetic Road Networks.
In: Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM'10), volume 6124 of Lecture Notes in Computer Science. Springer, 2010.
- Reinhard Bauer and Dorothea Wagner:
Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study.
In: Proceedings of the 8th International Symposium on Experimental Algorithms (SEA'09), Lecture Notes in Computer Science. Springer, June 2009.
[ pdf ] - Dorothea Wagner and Thomas Willhalm:
Drawing Graphs to Speed Up Shortest-Path Computations.
In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), pages 15-24. SIAM, 2005.
- Ulrik Brandes, Frank Schulz, Dorothea Wagner and Thomas Willhalm:
Generating Node Coordinates for Shortest-Path Computations in Transportation Networks.
ACM Journal of Experimental Algorithmics, 9:1-16, 2004.
[ html ] - Ulrik Brandes, Frank Schulz, Dorothea Wagner and Thomas Willhalm:
Travel Planning with Self-Made Maps.
In: Proceedings of the 3rd International Workshop on Algorithm Engineering and Experiments (ALENEX'01), volume 2153 of Lecture Notes in Computer Science, pages 132-144. Springer, 2001.
[ html | pdf ]
Related
- Martin Holzer, Grigorios Prasinos, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis:
Engineering Planar Separator Algorithms.
In: Proceedings of the 13th European Symposium on Algorithms (ESA 2005), volume 3669 of LNCS, pages 628-639. Springer, October 2005.
[ pdf ] - Annegret Liebers, Dorothea Wagner, and Karsten Weihe:
On the Hardness of Recognizing Bundles in Time Table Graphs.
In: Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), volume 657 of Lecture Notes in Computer Science, pages 325-337. Springer, 1999.
[ html ]