CoChat
Sign Up
Cited by 190Complexity and Algorithms in GraphsGraph Theory and AlgorithmsTransportation Planning and Optimization

The DOI matches its Crossref record.

Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm

Bauer, Reinhard, Delling, Daniel, Sanders, Peter, Schieferdecker, Dennis, Schultes, Dominik, Wagner, Dorothea·2010·ACM Journal of Experimental Algorithmics
DOI 10.1145/1671970.1671976
Open this paper in CoChat — free account

Abstract

In recent years, highly effective hierarchical and goal-directed speed-up techniques for routing in large road networks have been developed. This article makes a systematic study of combinations of such techniques. These combinations turn out to give the best results in many scenarios, including graphs for unit disk graphs, grid networks, and time-expanded timetables. Besides these quantitative results, we obtain general insights for successful combinations.

Overview

Integrity signals

Registry

Crossref · 10.1145/1671970.1671976

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 41

  1. Bast , H. , Funke , S. , Matijevic , D. , Sanders , P. , and Schultes , D . 2007. In transit to constant shortest-path queries in road networks . In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07) . SIAM, Philadelphia, 46--59. Bast, H., Funke, S., Matijevic, D., Sanders, P., and Schultes, D. 2007. In transit to constant shortest-path queries in road networks. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07). SIAM, Philadelphia, 46--59.
  2. 10.1126/science.1137521 · DOI
  3. Batz , G. V. , Delling , D. , Sanders , P. , and Vetter , C . 2009. Time-dependent contraction hierarchies . In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09) . SIAM, Philadelphia, 97--105. Batz, G. V., Delling, D., Sanders, P., and Vetter, C. 2009. Time-dependent contraction hierarchies. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09). SIAM, Philadelphia, 97--105.
  4. Bauer , R. and Delling , D . 2008. SHARC: Fast and robust unidirectional routing . In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08) . SIAM, Philadelphia, 13--26. Bauer, R. and Delling, D. 2008. SHARC: Fast and robust unidirectional routing. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08). SIAM, Philadelphia, 13--26.
  5. 10.1145/1498698.1537599 · DOI
  6. Bauer , R. , Delling , D. , Sanders , P. , Schieferdecker , D. , Schultes , D. , and Wagner , D . 2008. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm . In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08) . Springer, Berlin, 303--318. Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., and Wagner, D. 2008. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08). Springer, Berlin, 303--318.
  7. Bauer , R. , Delling , D. , and Wagner , D . 2007. 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) . Bauer, R., Delling, D., and Wagner, D. 2007. 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).
  8. Beier R. Funke S. Matijevic D. and Sanders P. 2009. Energy-efficient paths in radio networks. Algorithmica. Beier R. Funke S. Matijevic D. and Sanders P. 2009. Energy-efficient paths in radio networks. Algorithmica. · DOI
  9. 10.1006/jagm.2001.1189 · DOI
  10. Dantzig , G. B. 1962. Linear Programming and Extensions . Princeton University Press . Dantzig, G. B. 1962. Linear Programming and Extensions. Princeton University Press.
  11. 10.1007/978-3-540-87744-8_28 · DOI
  12. Delling D. 2009. Time-dependent SHARC-routing. Algorithmica. Delling D. 2009. Time-dependent SHARC-routing. Algorithmica. · DOI
  13. 10.1007/978-3-540-92182-0_71 · DOI
  14. Delling , D. , Pajor , T. , and Wagner , D . 2008. 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) . Delling, D., Pajor, T., and Wagner, D. 2008. 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).
  15. 10.1007/978-3-642-02094-0_7 · DOI
  16. Delling , D. , Sanders , P. , Schultes , D. , and Wagner , D . 2009b. Highway hierarchies star. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson , Eds. DIMACS Book , vol. 74 . American Mathematical Society, Providence, RI, 141--174. Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2009b. Highway hierarchies star. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds. DIMACS Book, vol. 74. American Mathematical Society, Providence, RI, 141--174.
  17. Delling , D. and Wagner , D . 2007. Landmark-based routing in dynamic graphs . In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07) . Springer, Berlin, 52--65. Delling, D. and Wagner, D. 2007. Landmark-based routing in dynamic graphs. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, Berlin, 52--65.
  18. 10.1007/978-3-642-02011-7_13 · DOI
  19. Demetrescu , C. , Goldberg , A. V. , and Johnson , D. S. , Eds . 2006 . Proceedings of the 9th DIMACS Implementation Challenge—Shortest Paths. American Mathematical Society , Providence, RI. Demetrescu, C., Goldberg, A. V., and Johnson, D. S., Eds. 2006. Proceedings of the 9th DIMACS Implementation Challenge—Shortest Paths. American Mathematical Society, Providence, RI.
  20. 10.1007/BF01386390 · DOI
  21. Geisberger , R. , Sanders , P. , Schultes , D. , and Delling , D . 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks . In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08) .Springer, Berlin, 319--333. Geisberger, R., Sanders, P., Schultes, D., and Delling, D. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08).Springer, Berlin, 319--333.
  22. Goldberg , A. V. and Harrelson , C . 2005. Computing the shortest path: A* search meets graph theory . In Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'05) . ACM, New York, 156--165. Goldberg, A. V. and Harrelson, C. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'05). ACM, New York, 156--165.
  23. Goldberg , A. V. , Kaplan , H. , and Werneck , R. F . 2006. Reach for A*: Efficient point-to-point shortest path algorithms . In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06) . SIAM, Philadelphia, 129--143. Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2006. Reach for A*: Efficient point-to-point shortest path algorithms. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06). SIAM, Philadelphia, 129--143.
  24. Goldberg , A. V. , Kaplan , H. , and Werneck , R. F . 2007. Better landmarks within reach . In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07) . Springer, Berlin, 38--51. Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2007. Better landmarks within reach. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, Berlin, 38--51.
  25. Goldberg , A. V. , Kaplan , H. , and Werneck , R. F . 2009. Reach for A*: shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson , Eds. DIMACS Book , vol. 74 . American Mathematical Society, Providence, RI, 93--139. Goldberg, A. V., Kaplan, H., and Werneck, R. F. 2009. Reach for A*: shortest path algorithms with preprocessing. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds. DIMACS Book, vol. 74. American Mathematical Society, Providence, RI, 93--139.
  26. Goldberg , A. V. and Werneck , R. F . 2005. Computing point-to-point shortest paths from external, emory . In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05) . SIAM, Philadelphia, 26--40. Goldberg, A. V. and Werneck, R. F. 2005. Computing point-to-point shortest paths from external, emory. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05). SIAM, Philadelphia, 26--40.
  27. Gutman , R. J. 2004 . Reach-based routing: A new approach to shortest path algorithms optimized for road networks . In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04) . SIAM, Philadelphia, 100--111. Gutman, R. J. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04). SIAM, Philadelphia, 100--111.
  28. Hilger , M. , Köhler , E. , Möhring , R. H. , and Schilling , H . 2009. Fast point-to-point shortest path computations with ArcFlags. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson , Eds. DIMACS Book , vol. 74 . American Mathematical Society, Providence, RI, 41--72. Hilger, M., Köhler, E., Möhring, R. H., and Schilling, H. 2009. Fast point-to-point shortest path computations with ArcFlags. In The Shortest Path Problem: Ninth DIMACS Implementation Challenge, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds. DIMACS Book, vol. 74. American Mathematical Society, Providence, RI, 41--72.
  29. Holzer , M. , Schulz , F. , and Wagner , D . 2006. Engineering multi-level overlay graphs for shortest-path queries . In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06) . SIAM, Philadelphia, 156--170. Holzer, M., Schulz, F., and Wagner, D. 2006. Engineering multi-level overlay graphs for shortest-path queries. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX'06). SIAM, Philadelphia, 156--170.
  30. 10.1145/1064546.1180616 · DOI
  31. Holzer , M. , Schulz , F. , and Willhalm , T . 2004. Combining speed-up techniques for Shortest path computations . In Proceedings of the 3rd Workshop on Experimental Algorithms (WEA'04) . Springer, Berlin, 269--284. Holzer, M., Schulz, F., and Willhalm, T. 2004. Combining speed-up techniques for Shortest path computations. In Proceedings of the 3rd Workshop on Experimental Algorithms (WEA'04). Springer, Berlin, 269--284.
  32. 10.1007/11427186_13 · DOI
  33. Lauther , U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background . In Geoinformation und Mobilität - von der Forschung zur praktischen Anwendung. vol. 22 . IfGI , 219--230. Lauther, U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität - von der Forschung zur praktischen Anwendung. vol. 22. IfGI, 219--230.
  34. 10.1007/11427186_18 · DOI
  35. Pellegrini , F. 2007 . SCOTCH: Static mapping, graph, mesh and hyper-graph partitioning, and parallel and sequential sparse matrix ordering package . http://www.labri.fr/perso/pelegrin/scotch/. Pellegrini, F. 2007. SCOTCH: Static mapping, graph, mesh and hyper-graph partitioning, and parallel and sequential sparse matrix ordering package. http://www.labri.fr/perso/pelegrin/scotch/.
  36. 10.1007/11561071_51 · DOI
  37. 10.1007/11841036_71 · DOI
  38. Schultes , D. and Sanders , P . 2007. Dynamic highway-node routing . In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07) . Springer, Berlin, 66--79. Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07). Springer, Berlin, 66--79.
  39. 10.1145/351827.384254 · DOI
  40. Schulz , F. , Wagner , D. , and Zaroliagis , C . 2002. Using multi-level graphs for timetable information in railway systems . In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02) . Springer, Berlin, 43--59. Schulz, F., Wagner, D., and Zaroliagis, C. 2002. Using multi-level graphs for timetable information in railway systems. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02). Springer, Berlin, 43--59.
  41. 10.1145/1064546.1103378 · DOI

Cited by

Metadata

Authors
Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., & Wagner, D.
Affiliations
Karlsruhe Institute of Technology (DE)
ORCID
Venue
ACM Journal of Experimental Algorithmics
Publisher
Association for Computing Machinery (ACM)
Published
2010-03
Volume
15
ISSN
1084-6654 (ISSN-L)
DOI
10.1145/1671970.1671976
OpenAlex
W2150418461
Cited by
190
References
0
Citations by year
2026: 2 · 2025: 5 · 2024: 6 · 2023: 7 · 2022: 7 · 2021: 12 · 2020: 9 · 2019: 16 · 2018: 3 · 2017: 9 · 2016: 4 · 2015: 15 · 2014: 12 · 2013: 22 · 2012: 19
FWCI
22.10
Type
journal article
Language
en
Open access
closed
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
ACM Journal of Experimental Algorithmics (publishedVersion)
Funders
  • Deutsche Forschungsgemeinschaft (SA 933/1-3SA 933/5-1WA 654/16-1)
  • Research Training Group (1194)
  • Seventh Framework Programme (FP6-021235-2)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
  • Social Sciences › Transportation › Transportation Planning and Optimization
Keywords
Dijkstra's algorithm, shortest path algorithms, road network routing, unit disk graphs, grid networks, time-expanded network, timetable optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review