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

graph algorithmshortest pathsVC-dimension

Mathematics Subject Classification ID

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

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

(28)

• Computation and growth of road network dimensions
• \(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension
• An efficient noisy binary search in graphs via Median approximation
• Eccentricity queries and beyond using hub labels
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Polynomial time approximation schemes for clustering in low highway dimension graphs
• Sublinear search spaces for shortest path planning in grid and road networks
• On the complexity of hub labeling (extended abstract)
• VC-dimension and shortest path algorithms
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• Lower bounds in the preprocessing and query phases of routing 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
• Computing constrained shortest-paths at scale
• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
• Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
• The parameterized hardness of the \(k\)-center problem in transportation networks
• A (1+\varepsilon)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Highway dimension, shortest paths, and provably efficient algorithms
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Travelling on graphs with small highway dimension
• Generalized \(k\)-center: distinguishing doubling and highway dimension
• Exact and approximate hierarchical hub labeling
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Generalized k-center: distinguishing doubling and highway dimension
• Parameterized upper bounds for path-consistent hub labeling
• Sublinear average-case shortest paths in weighted unit-disk graphs

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)