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:
 [1] Anderson, R.J.; Miller, G.L., Deterministic parallel List ranking, (), 81-90 [2] 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) [3] Berkman, O.; Vishkin, U., Recursive *-tree parallel data-structure, (), 196-202, SIAM J. Comput., to appear [4] Berkman, O.; Vishkin, U., Recursive *-tree parallel data-structure, (), SIAM J. Comput., to appear · Zbl 0770.68044 [5] Berkman, O.; Vishkin, U., Almost fully-parallel parentheses matching, () · Zbl 0814.68071 [6] Chazelle, B., Computing on a free tree via complexity-preserving mappings, Algorithmica, 2, 337-361, (1987) · Zbl 0636.68092 [7] Cole, R.; Vishkin, U., Approximate and exact parallel scheduling with applications to List, tree and graph problems, (), 478-491 [8] Cole, R.; Vishkin, U., Faster optimal parallel prefix sums and List ranking, Inform. and comput., 81, No. 3, 334-352, (1989) · Zbl 0684.68048 [9] Dietz, P.F., Finding level-ancestors in dinamic trees, manuscript, (1991) [10] 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 [11] Harel, D.; Tarjan, R.E., Fast algorithms for finding nearest common ancestors, SIAM J. comput., 13, No. 2, 338-355, (1984) · Zbl 0535.68022 [12] Ladner, R.E.; Fischer, M.J., Parallel prefix computation, J. assoc. comput. Mach., 27, 831-838, (1980) · Zbl 0445.68066 [13] Manber, U., Recognizing breadth-first search trees in linear time, Inform. process. lett., 34, 167-171, (1990) · Zbl 0696.68065 [14] Stone, H.S., Parallel tridiagonal equation solvers, ACM trans. math. software, 1, No. 4, 289-307, (1975) · Zbl 0315.65018 [15] Shiloach, Y.; Vishkin, U., Finding the maximum, merging, and sorting in a parallel computation model, J. algorithms, 2, 88-102, (1981) · Zbl 0456.68062 [16] Schieber, B.; Vishkin, U., On finding lowest common ancestors: simplification and parallelization, SIAM J. comput., 17, No. 6, 1253-1262, (1988) · Zbl 0669.68049 [17] Tarjan, R.E.; Vishkin, U., An efficient parallel, biconnectivity algorithm, SIAM J. comput., 14, No. 4, 862-874, (1985) · Zbl 0575.68066 [18] 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.