A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels

DOI10.1007/978-3-030-50026-9_26OpenAlexW3036078983MaRDI QIDQ5042258

Tobias Rupp, Stefan Funke

Publication date: 19 October 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-50026-9_26

zbMATH Keywords

route planningcontraction hierarchieshub labelling

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Sublinear search spaces for shortest path planning in grid and road networks
• Hierarchical Hub Labelings for Shortest Paths
• Fast Routing in Road Networks with Transit Nodes
• Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms
• Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
• A Separator Theorem for Planar Graphs
• Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
• Reach for A*: Efficient Point-to-Point Shortest Path Algorithms
• SHARC: Fast and Robust Unidirectional Routing
• Transit Nodes – Lower Bounds and Refined Construction
• Search-Space Size in Contraction Hierarchies
• Engineering highway hierarchies

This page was built for publication: A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels