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
Recommendations
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)
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 that?)
- 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)
