@book{3070414b1d63456b9210e28a8815f183,
title = "Identifying Nearest Common Ancestors in a Distributed Environment",
abstract = "We give a simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels assigned by out algorithm are of size O(log n) bits where n is the number of nodes on the tree. The algorithm runs in O(n) time.",
keywords = "nearest common ancestor, rooted tree, labeling algorithm, complexity analysis, information retrieval",
author = "Stephen Alstrup and Theis Rauhe and Cyril Gavoille and Haim Kaplan",
year = "2001",
month = aug,
language = "English",
series = "IT University Technical Report Series",
number = "TR-2001-6",
publisher = "IT-Universitetet i K{\o}benhavn",
address = "Denmark",
edition = "TR-2001-6",
}