Preprocessing Speed-Up Techniques Is Hard

DOI10.1007/978-3-642-13073-1_32zbMath1284.05263OpenAlexW1594459318MaRDI QIDQ3563016

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

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (8)

Search-space size in contraction hierarchies ⋮ Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms ⋮ Graph Bisection with Pareto Optimization ⋮ Unnamed Item ⋮ Shortest-path queries in static networks ⋮ Bundling all shortest paths ⋮ Unnamed Item ⋮ Customizable Contraction Hierarchies

This page was built for publication: Preprocessing Speed-Up Techniques Is Hard