Highway Dimension and Provably Efficient Shortest Path Algorithms

DOI10.1145/2985473zbMath1425.68447OpenAlexW2461311369MaRDI QIDQ3177817

Daniel Delling, Renato F. Werneck, Ittai Abraham, Andrew V. Goldberg, 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 algorithmVC-dimensionshortest paths

Mathematics Subject Classification ID

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

Related Items (19)

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 ⋮ Eccentricity queries and beyond using hub labels ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ On the Complexity of Hub Labeling (Extended Abstract) ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Sublinear search spaces for shortest path planning in grid and road networks ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Unnamed Item ⋮ Travelling on graphs with small highway dimension ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ \(\mathsf{W[1}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension] ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ An efficient noisy binary search in graphs via Median approximation ⋮ Computing Constrained Shortest-Paths at Scale

This page was built for publication: Highway Dimension and Provably Efficient Shortest Path Algorithms