A routing labeling scheme assigns a binary string, called a label, to each node in a network, and chooses a distinct port number from {1, …, d} for every edge outgoing from a node of degree d. Then, given the labels of u and w and no other information about the network, it should be possible to determine the port number corresponding to the first edge on the shortest path from u to w. In their seminal paper, Thorup and Zwick [SPAA 2001] designed several routing methods for general weighted networks. An important technical ingredient in their paper that according to the authors “may be of independent practical and theoretical interest” is a routing labeling scheme for trees of arbitrary degrees. For a tree on n nodes, their scheme constructs labels consisting of (1 + o(1)) log n bits such that the sought port number can be computed in constant time. Looking closer at their construction, the labels consist of bits. Given that the only known lower bound is log n + Ω(log log n), a natural question that has been asked for other labeling problems in trees is to determine the asymptotics of the smaller-order term. We make the first (and significant) progress in 19 years on determining the correct second-order term for the length of a label in a routing labeling scheme for trees on n nodes. We design such a scheme with labels of length .

Preprocessing a tree for finding the nearest common ancestor of two nodes is a basic tool with multiple applications. Quite a few linear-space constant-time solutions are known and the problem seems to be well-understood. This is however not so clear if we want to design a labeling scheme. In this model, the structure should be distributed: every node receives a distinct binary string, called its label, so that given the labels of two nodes (and no further information about the topology of the tree) we can compute the label of their nearest common ancestor. The goal is to make the labels as short as possible. Alstrup, Gavoille, Kaplan, and Rauhe [Theor. Comput. Syst. 37(3):441–456 2004] showed that O(log n)-bit labels are enough, with a somewhat large constant. More recently, Alstrup, Halvorsen, and Larsen [SODA 2014] refined this to only 2.772 log n, and provided a lower bound of 1.008 log n. We connect the question of designing a labeling scheme for nearest common ancestors to the existence of a tree, called a minor-universal tree, that contains every tree on n nodes as a topological minor. Even though it is not clear if a labeling scheme must be based on such a notion, we argue that all already existing schemes can be reformulated as such. Further, we show that this notion allows us to easily obtain clean and good bounds on the length of the labels. As the main upper bound, we show that 2.318 log n-bit labels are enough. Surprisingly, the notion of a minor-universal tree for binary trees on n nodes has been already used in a different context by Hrubes et al. [CCC 2010], and Young, Chu, and Wong [J. ACM 46(3):416–435, 1999] introduced a very closely related (but not equivalent) notion of a universal tree. On the lower bound side, we show that any minor-universal tree for trees on n nodes must contain at least Ω(n2.174) nodes. This highlights a natural limitation for all approaches based on defining a minor-universal tree. We complement the existential results with a generic transformation that allows us, for any labeling scheme for nearest common ancestors based on a minor-universal tree, to decrease the query time to constant, while increasing the length of the labels only by lower order terms.