On finding lowest common ancestors: Simplification and parallelization: Extended summary

Baruch Schieber, Uzi Vishkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationVLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings
EditorsJohn H. Reif
PublisherSpringer Verlag
Pages111-123
Number of pages13
ISBN (Print)9780387968186
DOIs
StatePublished - 1988
Externally publishedYes
Event3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988 - Corfu, Greece
Duration: Jun 28 1988Jul 1 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume319 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988
Country/TerritoryGreece
CityCorfu
Period6/28/887/1/88

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this