FINDING LEVEL-ANCESTORS IN TREES
FINDING LEVEL-ANCESTORS IN TREES
复制标题
DOI：
10.1016/s0022-0000(05)80002-9
复制
发表时间：
1994-04-01
影响因子：
1.1
通讯作者：
VISHKIN, U
中科院分区：
文献类型：
--
作者：
BERKMAN, O;VISHKIN, U
考虑水平祖先问题。假设给出一棵有根树 T 进行预处理。快速回答以下形式的询问。给定一个顶点 v 和一个整数 i > 0，找到从 v 到根的路径上的第 i 个顶点。给定任何 m，1 小于或等于 m 小于或等于 log* n，我们得到以下结果： (1) 使用最优数量的处理器进行预处理的 O(log(m) n)1 时间，如果 m 恒定，则使用单个处理器处理查询的恒定时间。 (2) 使用最佳数量的处理器进行预处理的时间为 O(log* n)，使用单个处理器处理查询的时间为 O(log* n)。这些结果假设树的欧拉之旅和每个顶点的级别（距根的距离）均已给出。如果没有这些假设，上述结果 (1) 的唯一变化是预处理时间增加到 O(log n)。直接的推论是预处理的串行线性时间限制和处理查询的恒定时间限制。 (C) 1994 年学术出版社
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 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 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. (C) 1994 Academic Press, Inc.