Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling

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

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

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 bound; hub labeling; distance labeling; Ruzsa-Szemeredi function

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68P05: Data structures