Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738 · cited 1×
“In [12, 13, 16] the ALT algorithm is presented that is based on A∗ search [18], Landmarks, and the Triangle inequality.”
MethodA Set of Measures of Centrality Based on Betweenness
Freeman, L. C. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,295
Linear Programming and Extensions
Dantzig, G. (1963) · RAND Corporation eBooks · doi:10.7249/r366 · Cited by 5,755
Computing the shortest path: A search meets graph theory
Goldberg, A. V., & Harrelson, C. (2005) · doi:10.5555/1070432.1070455 · Cited by 719
Highway Hierarchies Hasten Exact Shortest Path Queries
Sanders, P., & Schultes, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/11561071_51 · Cited by 327
Self-citationReach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks.
Gutmann, R. J. (2004) · Cited by 292
Anthonisse, J. M. (1971) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 277
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms
Goldberg, A. V., Kaplan, H., & Werneck, R. F. (2006) · 2006 Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX) · doi:10.1137/1.9781611972863.13 · Cited by 247
Fast Routing in Road Networks with Transit Nodes
Bast, H., Funke, S., Sanders, P., & Schultes, D. (2007) · Science · doi:10.1126/science.1137521 · Cited by 228
Self-citationCombining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., & Wagner, D. (2010) · ACM Journal of Experimental Algorithmics · doi:10.1145/1671970.1671976 · Cited by 190
Self-citationFast point-to-point shortest path computations with arc-flags
Hilger, M., Köhler, E., Möhring, R. H., & Schilling, H. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/03 · Cited by 184
Schultes, D., & Sanders, P. (2007) · Springer eBooks · doi:10.1007/978-3-540-72845-0_6 · Cited by 179
Self-citationEngineering Highway Hierarchies
Sanders, P., & Schultes, D. (2006) · Lecture Notes in Computer Science · doi:10.1007/11841036_71 · Cited by 172
Self-citationSHARC: Fast and robust unidirectional routing
Bauer, R., & Delling, D. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1498698.1537599 · Cited by 156
Self-citationPartitioning Graphs to Speed Up Dijkstra’s Algorithm
Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., & Willhalm, T. (2005) · Lecture notes in computer science · doi:10.1007/11427186_18 · Cited by 140
Computing Many-to-Many Shortest Paths Using Highway Hierarchies
Knopp, S., Sanders, P., Schultes, D., Schulz, F., & Wagner, D. (2007) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972870.4 · Cited by 132
Self-citationEngineering Fast Route Planning Algorithms
Sanders, P., & Schultes, D. (2007) · Springer eBooks · doi:10.1007/978-3-540-72845-0_2 · Cited by 118
Self-citationAcceleration of Shortest Path and Constrained Shortest Path Computation
Köhler, E., Möhring, R. H., & Schilling, H. (2005) · Lecture notes in computer science · doi:10.1007/11427186_13 · Cited by 108
Route Planning in Road Networks
Schultes, D. (2008) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000007755 · Cited by 99
Self-citationGoldberg, A. V., Kaplan, H. Y., & Werneck, R. F. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-72845-0_4 · Cited by 93
Goal-directed shortest-path queries using precomputed cluster distances
Maue, J., Sanders, P., & Matijević, D. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1498698.1564502 · Cited by 76
Self-citationDelling, D., Sanders, P., Schultes, D., & Wagner, D. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/06 · Cited by 65
Self-citationSanders, P., Schultes, D., & Vetter, C. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87744-8_61 · Cited by 54
Self-citationLauther, U. (2009) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/074/02 · Cited by 42
Hutchison, D., Sudan, M., Vardi, M. Y., Terzopoulos, D., Mattern, F., Tygar, D., Weikum, G., de Boer, F. S., Bonsangue, M. M., Graf, S., et al. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92188-2 · Cited by 30
Cited by
Benchmarks for Grid-Based Pathfinding
Sturtevant, N. R. (2012) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2012.2197681 · Cited by 549
Real-time routing with OpenStreetMap data
Luxen, D., & Vetter, C. (2011) · Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems · doi:10.1145/2093973.2094062 · Cited by 478
Engineering Route Planning Algorithms
Delling, D., Sanders, P., Schultes, D., & Wagner, D. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-02094-0_7 · Cited by 454
Self-citationExact Routing in Large Road Networks Using Contraction Hierarchies
Geisberger, R., Sanders, P., Schultes, D., & Vetter, C. (2012) · Transportation Science · doi:10.1287/trsc.1110.0401 · Cited by 323
Self-citationManaging Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey
Rigas, E. S., Ramchurn, S. D., & Bassiliades, N. (2015) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2014.2376873 · Cited by 280
“This strategy is based on the construction hierarchies technique [32], which removes nodes in an iterative manner and, at the same time, perceives the shortest path distances between the remaining nodes.”
Method
Metadata
- Authors
- Geisberger, R., Sanders, P., Schultes, D., & Delling, D.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2008-05-28
- Pages
- 319-333
- OpenAlex
- W2148831787
- Cited by
- 714
- References
- 27
- FWCI
- 23.19
- Type
- conference paper
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.