TITLE: Nearest Common Ancestors : A Survey and a new Distributed Algorithm
AUTHORS: Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe
ABSTRACT:
Several papers describe linear time algorithms to preprocess a tree,
such that one can answer subsequent nearest common ancestor queries in
constant time. Here, we survey these algorithms and related results.
A common idea used by all the algorithms for the problem is that a
solution for complete balanced binary trees is straightforward.
Furthermore, for complete balanced binary trees we can easily solve
the problem in a distributed way by labeling the nodes of the tree
such that from the labels of two nodes alone one can compute the label
of their nearest common ancestor. Whether it is possible to
distribute the data structure into short labels associated with the
nodes is important for several applications such as routing.
Therefore, related labeling problems have recieved a lot of attention
recently.
Previous optimal algorithms for nearest common ancestor queries work
using some mapping from a general tree to a completely balanced binary
tree. However, it is not clear how to distribute the data structures
obtained via these mappings. We conclude our survey with a new 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 our
algorithm are of size O(logn) bits where n is the number
of nodes in the tree. The algorithm runs in O(nn) time.