@inproceedings{15572833d15441fe8abd75b75b23317d,
title = "On finding lowest common ancestors: Simplification and parallelization: Extended summary",
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 which enables us to answer each query in O (1) time, as in Harel and Tarjan [HT-84]. 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.",
author = "Baruch Schieber and Uzi Vishkin",
note = "Funding Information: 1. Introduction We consider the following problem. Given a rooted tree T(V,E) for preprocessing, answer on-line LCA queries of the form, {"}Which vertex is the Lowest Common Ancestor (LCA) of x and y ?{"} for any pair of vertices x ,y in T. (Let us denote such a query LCA (x,y).) We present a preprocessing 1. The research of both authors was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract number DE-AC02-76ER03077. 2. The research of this author was supported by NSF grant NSF-CCR-8615337, ONR grant N00014-85-K-0046 and the Foundation for Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences and Humanities. 3. Current address: I.B.M. - Research Division, T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598. Publisher Copyright: {\textcopyright} 1988, Springer-Verlag.; 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988 ; Conference date: 28-06-1988 Through 01-07-1988",
year = "1988",
doi = "10.1007/BFb0040379",
language = "English (US)",
isbn = "9780387968186",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "111--123",
editor = "Reif, {John H.}",
booktitle = "VLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings",
address = "Germany",
}