Preprocessing speed-up techniques is hard

DOI10.1007/978-3-642-13073-1_32MaRDI QIDQ3563016zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(14)

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

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)