Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment |
| |
Authors: | Stephen Alstrup Cyril Gavoille Haim Kaplan and Theis Rauhe |
| |
Affiliation: | (1) Department of Theory, IT University of Copenhagen, Copenhagen DK-2400, Denmark;(2) LaBRI, Universite de Bordeaux, 33405 Talence cedex, France;(3) School of Computer Science, Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | Several papers describe linear time algorithms to preprocess a tree, in order to answer subsequent nearest common ancestor
queries in constant time. Here, we survey these algorithms and related results. Whereas previous algorithms produce a linear
space data structure, in this paper we address the problem of distributing the data structure into short labels associated
with the nodes. Localized data structures received much attention recently as they play an important role for distributed
applications such as routing. We conclude our survey with a new simple algorithm that labels in O(n) time all the nodes of
an n-node rooted tree such that from the labels of any 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|