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 (21)
- Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
- 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
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- Title not available (Why is that?)
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Travelling on graphs with small highway dimension
- Eccentricity queries and beyond using hub labels
- VC-dimension and shortest path algorithms
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- On the Complexity of Hub Labeling (Extended Abstract)
- The Parameterized Hardness of the k-Center Problem in Transportation Networks
- 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
- Computing Constrained Shortest-Paths at Scale
- 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)
