Algorithmic aspects of bijective tree encoding: a survey

We address the problem of labeling the nodes of a tree such that one can determine the identi¯er of the least common ancestor of any two nodes by looking only at their labels. This problem has applica- tion in routing and in distributed computing in peer-to-peer networks. A labeling scheme using £(log2 n)-bit labels has been presented by Peleg. By engineering this scheme and a new one due to the authors, we obtain a variety of data structures with the same asymptotic performances. We conduct a thorough experimental evaluation of all these data structures. Our results clearly show which variants achieve the best performances in terms of space usage, construction time, and query time