Highway dimension and provably efficient shortest path algorithms

DOI10.1145/2985473MaRDI QIDQ3177817zbMATH OpenOpenAlexFDO

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)

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