Distance labeling schemes for trees

Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, Ely Porat

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

181 Downloads (Pure)

Abstract

We consider distance labeling schemes for trees: given a tree with n nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the distance in the tree between the two nodes. A lower bound by Gavoille et al. [Gavoille et al., J. Alg., 2004] and an upper bound by Peleg [Peleg, J. Graph Theory, 2000] establish that labels must use Θ(log^2(n)) bits. Gavoille et al. [Gavoille et al., ESA, 2001] show that for very small approximate stretch, labels use Θ(log(n) log(log(n))) bits. Several other papers investigate various variants such as, for example, small distances in trees [Alstrup et al., SODA, 2003]. We improve the known upper and lower bounds of exact distance labeling by showing that 1/4 log2(n) bits are needed and that 1/2 log2(n) bits are sufficient. We also give (1 + ε)-stretch labeling schemes using Theta(log(n)) bits for constant ε> 0. (1 + ε)-stretch labeling schemes with polylogarithmic label size have previously been established for doubling dimension graphs by Talwar [Talwar, STOC, 2004]. In addition, we present matching upper and lower bounds for distance labeling for caterpillars, showing that labels must have size 2log n - Θ(log log n). For simple paths with k nodes and edge weights in [1,n], we show that labels must have size (k - 1)/k log n + Θ(log k).
Original languageEnglish
Title of host publicationProceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Publication date2016
Pages1-16
Article number132
ISBN (Print)978-3-95977-013-2
DOIs
Publication statusPublished - 2016
Event43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) - Rome, Italy
Duration: 12 Jul 201615 Jul 2016
Conference number: 43
http://easyconferences.eu/icalp2016/index.html

Conference

Conference43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Number43
CountryItaly
CityRome
Period12/07/201615/07/2016
Internet address

Bibliographical note

Published online and open access. Licensed under Creative Commons License CC-BY.

Keywords

  • Distributed computing
  • Distance labeling
  • Graph theory
  • Routing
  • Trees

Cite this

Alstrup, S., Gørtz, I. L., Bistrup Halvorsen, E., & Porat, E. (2016). Distance labeling schemes for trees. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (pp. 1-16). [132] https://doi.org/10.4230/LIPIcs.ICALP.2016.132