Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms

DOI10.1007/978-3-662-48350-3_84zbMath1466.68063arXiv1501.04262OpenAlexW2296308658MaRDI QIDQ3452861

Colin White

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.04262

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (4)

A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels ⋮ Unnamed Item ⋮ Sublinear search spaces for shortest path planning in grid and road networks ⋮ Computing Constrained Shortest-Paths at Scale

Cites Work

• On the Complexity of Hub Labeling (Extended Abstract)
• Preprocessing Speed-Up Techniques Is Hard
• Reachability and Distance Queries via 2-Hop Labels
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms