Paper Info
Title
Nearest common ancestors: a survey and a new distributed algorithm
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 binary trees is straightforward. Furthermore, for complete 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 received a lot of attention recently.Previous optimal algorithms for nearest common ancestor queries work using some mapping from a general tree to a complete binary tree. However, it is not clear how to distribute the data structures obtained using 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(\log n)$ bits where $n$ is the number of nodes in the tree. The algorithm runs in $O(n)$ time.
Year
DOI
Venue
2002
10.1145/564870.564914
SPAA
Keywords
Field
DocType
common idea,general tree,nearest common ancestor query,nearest common ancestor,rooted tree,distributed,complete binary tree,constant time,data structure,common ancestor query,labeling,linear time algorithm,ancestor,binary tree,distributed algorithm
2–3 tree,Combinatorics,Ball tree,Computer science,K-ary tree,Binary tree,Theoretical computer science,Exponential tree,(a,b)-tree,Interval tree,Cartesian tree
Conference
ISBN
Citations 
PageRank 
1-58113-529-7
50
2.42
References 
Authors
52
4
Name
Order
Citations
PageRank
Stephen Alstrup165742.60
Cyril Gavoille21526114.20
Haim Kaplan33581263.96
Theis Rauhe466135.11