Sublinear search spaces for shortest path planning in grid and road networks

DOI10.1007/S10878-021-00777-3MaRDI QIDQ2230730zbMATH OpenOpenAlexFDO

Authors Johannes Blum, Stefan Funke, Sabine Storandt

Publication date 28 September 2021

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10878-021-00777-3

zbMATH Keywords

shortest path planningbounded growth modelroad network dimensions

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Highway dimension and provably efficient shortest path algorithms
• Provable efficiency of contraction hierarchies with randomized preprocessing
• Engineering Highway Hierarchies
• Search-space size in contraction hierarchies
• Computation and growth of road network dimensions

Cites work

• scientific article; zbMATH DE number 7561636 (Why is no real title available?)
• Almost optimal set covers in finite VC-dimension
• Beyond highway dimension: small distance labels using tree skeletons
• Computation and growth of road network dimensions
• Customizable contraction hierarchies
• Distance labeling in graphs
• Distributed Computing
• Fast Routing in Road Networks with Transit Nodes
• Graph minors. V. Excluding a planar graph
• Hierarchy of Transportation Network Parameters and Hardness Results
• Highway dimension and provably efficient shortest path algorithms
• Highway dimension, shortest paths, and provably efficient algorithms
• Lower bounds in the preprocessing and query phases of routing algorithms
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Provable efficiency of contraction hierarchies with randomized preprocessing
• Robust distance queries on massive networks
• Search-space size in contraction hierarchies
• Transit nodes -- lower bounds and refined construction
• VC-dimension and shortest path algorithms
• -nets and simplex range queries

Cited in

(4)

• Search-space size in contraction hierarchies
• Computation and growth of road network dimensions
• A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels
• Search-space size in contraction hierarchies

This page was built for publication: Sublinear search spaces for shortest path planning in grid and road networks

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