{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T11:46:31Z","timestamp":1791027991728,"version":"4.1.0"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1988,12]]},"abstract":"<jats:p>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\u2013355]. 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.<\/jats:p>","DOI":"10.1137\/0217079","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:30:13Z","timestamp":1109226613000},"page":"1253-1262","source":"Crossref","is-referenced-by-count":359,"title":["On Finding Lowest Common Ancestors: Simplification and Parallelization"],"prefix":"10.1137","volume":"17","author":[{"given":"Baruch","family":"Schieber","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uzi","family":"Vishkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762122"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. Cole, U. Vishkin,  Approximate and exact parallel scheduling with applications to list, tree and graph problems,  Proc. 27th Annual IEEE Symposium on Foundations of Computer Science,  1986,  478\u2013491","DOI":"10.1109\/SFCS.1986.10"},{"key":"R4","unstructured":"R. Cole, U. Vishkin,  Faster optimal parallel prefix sums and list ranking, TR 56\/86, the Moise and Frida Eskenasy Institute of Computer Science, Tel Aviv University, Tel Aviv, Israel,  1986"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"G. M. Landau, U. Vishkin,  Introducing efficient parallelism into approximate string matching,  Proc. 18th Annual ACM Symposium on Theory of Computing,  1986,  220\u2013230","DOI":"10.1145\/12130.12152"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"G. M. Landau, B. Schieber, U. Vishkin,  Parallel construction of a suffix tree,  Proc. 14th Internat. Colloquium on Automata Language and Programming, Lecture Notes in Computer Science 267, Springer-Verlag, Berlin, New York,  1987,  314\u2013325","DOI":"10.1007\/3-540-18088-5_26"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90153-2"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676830"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"R11","unstructured":"U. Vishkin,  Synchronous parallel computation\u2014a survey, TR-71, Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, New York, NY,  1983"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90025-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0217079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:51Z","timestamp":1787338131000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0217079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,12]]},"references-count":12,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1988,12]]}},"alternative-id":["10.1137\/0217079"],"URL":"https:\/\/doi.org\/10.1137\/0217079","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,12]]}}}