Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
From MaRDI portal
Publication:4575838
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
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
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