SIAM Journal on Computing · 1984 · 1.1K citations · 8 references
ComputingComputer ScienceAlgorithmsData StructuresDatabasesNearest Neighbor SearchSublinear AlgorithmsNearest Neighbor Data StructuresTree AlgorithmsUniform-cost Search
We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y?” We 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, we present an algorithm for a random access machine with uniform cost measure (and a bound of $\Omega (\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, we obtain an almost-linear-time (and linear-space) algorithm.
8
Worst-case Analysis of Set Union Algorithms
Robert E. Tarjan, Jan Van Leeuwen · Journal of the ACM · 1984 · 458 citations · Full text
Applications of Path Compression on Balanced Trees
Robert E. Tarjan · Journal of the ACM · 1979 · 300 citations · Full text