# zbMATH — the first resource for mathematics

Finding level-ancestors in trees. (English) Zbl 0806.68027
Summary: The level-ancestor problem is considered. Suppose a rooted tree $$T$$ is given 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 path from $$v$$ to the root. Given any $$m$$, $$1 \leq m \leq \log^*n$$, we achieve the following results: (1) $$O(\log^{(m)}n)$$ time using an optimal number of processors for preprocessing and constant time using a single processor for processing a query if $$m$$ is constant. (2) $$O(\log^* n)$$ time using an optimal number of processors for preprocessing 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 these assumptions, the only change in result (1) above is that preprocessing time increases to $$O(\log n)$$. An immediate corollary is a serial linear-time bound for preprocessing and a constant-time bound for processing a query.

##### MSC:
 68P05 Data structures 68Q25 Analysis of algorithms and problem complexity
##### Keywords:
level-ancestor problem
Full Text:
##### References:
  Anderson, R.J.; Miller, G.L., Deterministic parallel List ranking, (), 81-90  Berkman, O.; Schieber, B.; Vishkin, U., Some doubly logarithmic parallel algorithms based on finding all nearest smaller values, (), also IBM research report, Computer Science, RC 14128 (#63291)  Berkman, O.; Vishkin, U., Recursive *-tree parallel data-structure, (), 196-202, SIAM J. Comput., to appear  Berkman, O.; Vishkin, U., Recursive *-tree parallel data-structure, (), SIAM J. Comput., to appear · Zbl 0770.68044  Berkman, O.; Vishkin, U., Almost fully-parallel parentheses matching, () · Zbl 0814.68071  Chazelle, B., Computing on a free tree via complexity-preserving mappings, Algorithmica, 2, 337-361, (1987) · Zbl 0636.68092  Cole, R.; Vishkin, U., Approximate and exact parallel scheduling with applications to List, tree and graph problems, (), 478-491  Cole, R.; Vishkin, U., Faster optimal parallel prefix sums and List ranking, Inform. and comput., 81, No. 3, 334-352, (1989) · Zbl 0684.68048  Dietz, P.F., Finding level-ancestors in dinamic trees, manuscript, (1991)  Fich, F.E.; Ragde, P.L.; Wigderson, A., Relations between concurrent-write models of parallel computation, SIAM J. comput., 1, 606-627, (1988) · Zbl 0652.68065  Harel, D.; Tarjan, R.E., Fast algorithms for finding nearest common ancestors, SIAM J. comput., 13, No. 2, 338-355, (1984) · Zbl 0535.68022  Ladner, R.E.; Fischer, M.J., Parallel prefix computation, J. assoc. comput. Mach., 27, 831-838, (1980) · Zbl 0445.68066  Manber, U., Recognizing breadth-first search trees in linear time, Inform. process. lett., 34, 167-171, (1990) · Zbl 0696.68065  Stone, H.S., Parallel tridiagonal equation solvers, ACM trans. math. software, 1, No. 4, 289-307, (1975) · Zbl 0315.65018  Shiloach, Y.; Vishkin, U., Finding the maximum, merging, and sorting in a parallel computation model, J. algorithms, 2, 88-102, (1981) · Zbl 0456.68062  Schieber, B.; Vishkin, U., On finding lowest common ancestors: simplification and parallelization, SIAM J. comput., 17, No. 6, 1253-1262, (1988) · Zbl 0669.68049  Tarjan, R.E.; Vishkin, U., An efficient parallel, biconnectivity algorithm, SIAM J. comput., 14, No. 4, 862-874, (1985) · Zbl 0575.68066  Vishkin, U., On efficient parallel strong orientation, Inform. process. lett., 20, 235-240, (1985) · Zbl 0603.68067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.