1988/12/01 by Baruch Schieber, Uzi Vishkin · 3 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Machine Learning and Algorithms #Error Correcting Code Techniques #Parallelizable manifold #Computer science #Preprocessor #Logarithm #Data structure #Combinatorics #Simple (philosophy) #Linear space #Parallel algorithm #Tree (set theory) #Time complexity #Algorithm #Parallel computing #Mathematics #Discrete mathematics
paper · doi:10.1137/0217079
openalex publication_date 1988/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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.