Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

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

Laurent Viennot, Adrian Kosowski

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

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

05C12: Distance in graphs

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

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

05C85: Graph algorithms (graph-theoretic aspects)