FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS.

Research output: Contribution to journalArticle

787 Scopus citations

Abstract

The authors consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, 'What is the nearest common ancestor of vertices x and y? ' They show that any pointer machine that solves this problem requires OMEGA (log log n) time per query in the worst case, where n is the total number of vertices in the trees. On the other hand, they present an algorithm for a random access machine with uniform cost measure (and a bound of O(log n) on the number of bits per word) that requires O(1) time per query and O(n) preprocessing time, assuming that the collection of trees is static. For a version of the problem in which the trees can change between queries, they obtain an almost-linear-time (and linear-space) algorithm.

Original languageEnglish (US)
Pages (from-to)338-355
Number of pages18
JournalSIAM Journal on Computing
Volume13
Issue number2
DOIs
StatePublished - Jan 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS.'. Together they form a unique fingerprint.

  • Cite this