Optimal Distance Labeling Schemes for Trees
Ofer Freedman, Paweł Gawrychowski, Patrick K. Nicholson, Oren Weimann · 2017
Labeling schemes seek to assign a short label to each node in a network, so that a function on two nodes (such as distance or adjacency) can be computed by examining their labels alone. For the particular case of trees, following a long line of research, optimal bounds (up to low order terms) were recently obtained for adjacency labeling [FOCS '15], nearest common ancestor labeling [SODA '14], and ancestry labeling [SICOMP '06]. In this paper we obtain optimal bounds for distance labeling. We present labels of size 1/4\log^2n+o(\log^2n), matching (up to low order terms) the recent 1/4\log^2n-\Oh(\log n) lower bound [ICALP '16].