Distance labeling schemes for trees

TY - GEN

T1 - Distance labeling schemes for trees

AU - Alstrup, Stephen

AU - Gørtz, Inge Li

AU - Halvorsen, Esben Bistrup

AU - Porat, Ely

N1 - Conference code: 43

PY - 2016/8/1

Y1 - 2016/8/1

N2 - 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 ⊖(log2 n) bits1. 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 ⊖(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 2 log n⊖(log log n). For simple paths with k nodes and edge weights in [1, n], we show that labels must have size (k1)/k log n + ⊖(log k).

AB - 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 ⊖(log2 n) bits1. 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 ⊖(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 2 log n⊖(log log n). For simple paths with k nodes and edge weights in [1, n], we show that labels must have size (k1)/k log n + ⊖(log k).

U2 - 10.4230/LIPIcs.ICALP.2016.132

DO - 10.4230/LIPIcs.ICALP.2016.132

M3 - Article in proceedings

SN - 978-3-95977-013-2

T3 - Leibniz International Proceedings in Informatics

BT - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Colloquium on Automata, Languages, and Programming 2016

Y2 - 12 July 2016 through 15 July 2016

ER -