On finding lowest common ancestors: Simplification and parallelization

Baruch Schieber, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

368 Scopus citations

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. 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.

Original languageEnglish (US)
Pages (from-to)1253-1262
Number of pages10
JournalSIAM Journal on Computing
Volume17
Issue number6
DOIs
StatePublished - Jan 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On finding lowest common ancestors: Simplification and parallelization'. Together they form a unique fingerprint.

Cite this