%0 Journal Article %1 schieber1988finding %A Schieber, Baruch %A Vishkin, Uzi %D 1988 %J SIAM Journal on Computing %K MRCA algorithms %N 6 %P 1253-1262 %R 10.1137/0217079 %T On Finding Lowest Common Ancestors: Simplification and Parallelization %U https://doi.org/10.1137/0217079 %V 17 %X We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm that enables us to answer each query in \$O(1)\$ time, as in Harel and Tarjan SIAM J. Comput., 13 (1984), pp. 338–355. Our algorithm has the advantage of being simple and easily parallelizable. The resulting parallel preprocessing algorithm runs in logarithmic time using an optimal number of processors on an EREW PRAM. Each query is then answered in \$O(1)\$ time using a single processor.

@article{schieber1988finding, abstract = { We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm that enables us to answer each query in \$O(1)\$ time, as in Harel and Tarjan [SIAM J. Comput., 13 (1984), pp. 338–355]. Our algorithm has the advantage of being simple and easily parallelizable. The resulting parallel preprocessing algorithm runs in logarithmic time using an optimal number of processors on an EREW PRAM. Each query is then answered in \$O(1)\$ time using a single processor. }, added-at = {2023-07-06T20:29:24.000+0200}, author = {Schieber, Baruch and Vishkin, Uzi}, biburl = {https://www.bibsonomy.org/bibtex/24c07d3e31de193cdf681ece509d376bc/peter.ralph}, doi = {10.1137/0217079}, eprint = {https://doi.org/10.1137/0217079}, interhash = {ce89f295bbc9db9843d3bea18926a1b0}, intrahash = {4c07d3e31de193cdf681ece509d376bc}, journal = {SIAM Journal on Computing}, keywords = {MRCA algorithms}, number = 6, pages = {1253-1262}, timestamp = {2023-07-06T20:30:26.000+0200}, title = {On Finding Lowest Common Ancestors: Simplification and Parallelization}, url = {https://doi.org/10.1137/0217079 }, volume = 17, year = 1988 }