On local representation of distances in trees
Cyril Gavoille, Arnaud Labourel · 2007
We consider distributed representation scheme for trees, supporting some special relationships between nodes at small distance. For instance, we show that for a tree T and an integer k we can assign local information on nodes such that we can decide for two nodes u and v if the distance between u and v is at most k and if so, compute it only using the local information assigned. For trees withn nodes, the local information assigned by our scheme is binary label of log n + O(klog(klog(n/k))) bits, improving a recent result of Alstrup, Bille and Rauhe.