Preprocessing speed-up techniques is hard

DOI10.1007/978-3-642-13073-1_32zbMATH Open1284.05263OpenAlexW1594459318MaRDI QIDQ3563016FDOQ3563016

Authors: Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, Dorothea Wagner 

Publication date: 28 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://publikationen.bibliothek.kit.edu/1000016080/1978704

Recommendations

• Speed-Up Techniques for Shortest-Path Computations
• Shortest path calculation in large road networks
• Point-to-Point Shortest Path Algorithms with Preprocessing
• Engineering Highway Hierarchies
• Reach for \(A^*\): shortest path algorithms with preprocessing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Cited In (13)

• Lower bounds in the preprocessing and query phases of routing algorithms
• Customizable contraction hierarchies
• Title not available (Why is that?)
• Speed-Up Techniques for Shortest-Path Computations
• Optimal forks: preprocessing single-source shortest path instances with interval data
• Exact distance oracles for planar graphs
• Precomputation techniques for the stochastic on-time arrival problem
• Search-space size in contraction hierarchies
• Preprocessing for segment routing optimization
• Shortest-path queries in static networks
• Bundling all shortest paths
• Graph bisection with Pareto optimization
• On the complexity of partitioning graphs for arc-flags

This page was built for publication: Preprocessing speed-up techniques is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3563016)