Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica, DIS
via Salaria 113, II piano
Aula C2

Abstract:
The nearest common ancestor (NCA) of two nodes in a rooted tree, is the common ancestor of the two nodes, with largest depth. In the talk we survey previous results for NCA, and give a new simple optimal algorithm. Our algorithm, opposite to previous, label the nodes of the tree, such that given the label of two nodes, one can compute alone from these labels, the label of nearest common ancestor of the two nodes. The algorithm runs in linear time and the length of the labels assigned to the nodes is O(log n),

Joint work with Haim Kaplan, Cyril Gaviolle, and Theis Rauhe.