Institut für Theoretische Informatik, Algorithmik

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 ]
  • Frank Schulz:
    Timetable information and shortest paths.
    PhD thesis, Universität Karlsruhe (TH), Fakultät Informatik, 2005.
    [ html | pdf | ps ]
  • 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 ]
  • Daniel Delling and Dorothea Wagner:
    Landmark-Based Routing in Dynamic Graphs.
    In: Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), volume 4525 of Lecture Notes in Computer Science, pages 52-65. Springer, June 2007.
    [ html | 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.
  • 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 ]
  • 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 ]
  • Horst W. Hamacher, Annegret Liebers, Anita Schöbel, Dorothea Wagner, and Frank Wagner:
    Locating New Stops in a Railway Network.
    In: Proceedings of ATMOS Workshop 2003, pages 13-23, 2004.
    [ html | pdf ]
  • Flavia Mammana, Steffen Mecke, and Dorothea Wagner:
    The Station Location Problem on Two Intersecting Lines.
    In: Proceedings of ATMOS Workshop 2003, pages 52-64, 2004.
    [ html | pdf ]
  • Ulrik Brandes and Dorothea Wagner:
    Using Graph Layout to Visualize Train Interconnection Data.
    In: Proceedings of the 6th International Symposium on Graph Drawing (GD'98), volume 1547 of Lecture Notes in Computer Science, pages 44-56. Springer, January 1999..
    [ html | 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 ]