查看文章

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].

Prior to our work, all distance labeling schemes for trees could be reinterpreted as universal trees. A tree T is said to be universal if any tree on nodes can be found as a subtree of T. A universal tree with |T| nodes implies a distance labeling scheme with label size \log |T|. In 1981 …