TY - JOUR
T1 - FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS.
AU - Harel, Dov
AU - Tarjan, Robert Endre
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 1984
Y1 - 1984
N2 - The authors consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, 'What is the nearest common ancestor of vertices x and y? ' They show that any pointer machine that solves this problem requires OMEGA (log log n) time per query in the worst case, where n is the total number of vertices in the trees. On the other hand, they present an algorithm for a random access machine with uniform cost measure (and a bound of O(log n) on the number of bits per word) that requires O(1) time per query and O(n) preprocessing time, assuming that the collection of trees is static. For a version of the problem in which the trees can change between queries, they obtain an almost-linear-time (and linear-space) algorithm.
AB - The authors consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, 'What is the nearest common ancestor of vertices x and y? ' They show that any pointer machine that solves this problem requires OMEGA (log log n) time per query in the worst case, where n is the total number of vertices in the trees. On the other hand, they present an algorithm for a random access machine with uniform cost measure (and a bound of O(log n) on the number of bits per word) that requires O(1) time per query and O(n) preprocessing time, assuming that the collection of trees is static. For a version of the problem in which the trees can change between queries, they obtain an almost-linear-time (and linear-space) algorithm.
UR - http://www.scopus.com/inward/record.url?scp=0021426157&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0021426157&partnerID=8YFLogxK
U2 - 10.1137/0213024
DO - 10.1137/0213024
M3 - Article
AN - SCOPUS:0021426157
VL - 13
SP - 338
EP - 355
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
SN - 0097-5397
IS - 2
ER -