Nearest Common Ancestors: Universal Trees and Improved Labeling Schemes

2017/07/27 by Fabian Kuhn, Fabian Kühn, Κωνσταντίνος Παναγιώτου +5
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1707.08807

arxiv created 2017/07/27 · openalex publication_date 2017/07/27 · arxiv updated 2017/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the nearest common ancestor (NCA) function in rooted trees. As the main conceptual contribution, the paper introduces universal trees for the NCA function: For a given family of rooted trees, an NCA-universal tree S is a rooted tree such that any tree T of the family can be embedded into S such that the embedding of the NCA in T of two nodes of T is equal to the NCA in S of the embeddings of the two nodes. As the main technical result we give explicit constructions of NCA-universal trees of size n^2.318 for the family of rooted n-vertex trees and of size n^1.894 for the family of rooted binary n-vertex trees. A direct consequence is the explicit construction of NCA-labeling schemes with labels of size 2.318log₂ n and 1.894log₂ n for the two families of rooted trees. This improves on the best known such labeling schemes established by Alstrup, Halvorsen and Larsen [SODA 2014].

Related

• Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
• A Data Structure for Nearest Common Ancestors with Linking
• A simple and optimal ancestry labeling scheme for trees
• A Simple Linear-Time Algorithm for the Common Refinement of Rooted Phylogenetic Trees on a Common Leaf Set
• Universal rooted phylogenetic tree shapes and universal tanglegrams