Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

DOI10.1137/1.9781611974782.95zbMath1410.68302arXiv1609.00512OpenAlexW2964124596MaRDI QIDQ4575838

Adrian Kosowski, Laurent Viennot

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.00512

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels ⋮ Unnamed Item ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Sublinear search spaces for shortest path planning in grid and road networks ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Unnamed Item ⋮ Travelling on graphs with small highway dimension ⋮ \(\mathsf{W[1}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension] ⋮ An efficient noisy binary search in graphs via Median approximation ⋮ Computing Constrained Shortest-Paths at Scale

This page was built for publication: Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons