Nearest Common Ancestors: Universal Trees and Improved Labeling Schemes

Fabian Kuhn, Konstantinos Panagiotou, Pascal Su

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 giv…