Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling

DOI10.1145/3293611.3331625zbMath1470.68047arXiv1902.07055OpenAlexW2963657803MaRDI QIDQ5145219

Przemysław Uznański, Adrian Kosowski, Laurent Viennot

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundhub labelingdistance labelingRuzsa-Szemeredi function

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (max. 100)

Better distance labeling for unweighted planar graphs ⋮ Eccentricity queries and beyond using hub labels ⋮ Unnamed Item ⋮ Better distance labeling for unweighted planar graphs ⋮ Isometric Universal Graphs

This page was built for publication: Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling