Highway dimension and provably efficient shortest path algorithms

DOI10.1145/2985473zbMATH Open1425.68447OpenAlexW2461311369MaRDI QIDQ3177817FDOQ3177817

Authors Ittai Abraham, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck, Amos Fiat 

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2985473

zbMATH Keywords

shortest pathsgraph algorithmVC-dimension

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Paths and cycles (05C38)

Recommendations

• Highway dimension, shortest paths, and provably efficient algorithms
• Engineering Highway Hierarchies
• Engineering highway hierarchies
• Algorithms – ESA 2005
• VC-dimension and shortest path algorithms

Cited In (25)

• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
• Lower bounds in the preprocessing and query phases of routing algorithms
• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• Exact and approximate hierarchical hub labeling
• An efficient noisy binary search in graphs via Median approximation
• Polynomial time approximation schemes for clustering in low highway dimension graphs
• Sublinear search spaces for shortest path planning in grid and road networks
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Generalized \(k\)-center: distinguishing doubling and highway dimension
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Computing constrained shortest-paths at scale
• Title not available (Why is no real title available?)
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• On the complexity of hub labeling (extended abstract)
• Computation and growth of road network dimensions
• Travelling on graphs with small highway dimension
• Eccentricity queries and beyond using hub labels
• VC-dimension and shortest path algorithms
• Highway dimension, shortest paths, and provably efficient algorithms
• Provable efficiency of contraction hierarchies with randomized preprocessing
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• \(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• The parameterized hardness of the \(k\)-center problem in transportation networks

This page was built for publication: Highway dimension and provably efficient shortest path algorithms

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