FINDING LEVEL-ANCESTORS IN TREES

The level-ancestor problem is considered. Suppose a rooted tree T is g iven for preprocessing. Answer quickly queries of the following form. Given a vertex v and an integer i > 0, find the i th vertex on the pat h from v to the root. Given any m, 1 less-than-or-equal-to m less-than -or-equal-to log n, we achieve the following results: (1) O(log(m) n) 1 time using an optimal number of processors for preprocessing and con stant time using a single processor for processing a query if m is con stant. (2) O(log n) time using an optimal number of processors for pr eprocessing and O(log n) time using a single processor for processing a query. These results assume that the Euler tour of the tree and the level (distance from the root) of each vertex are given. Without thes e assumptions, the only change in result (1) above is that preprocessi ng time increases to O(log n) An immediate corollary is a serial linea r-time bound for preprocessing and a constant-time bound for processin g a query. (C) 1994 Academic Press, Inc.