The LCA Problem Revisited
Bender, Michael A.
Farach-Colton, Martin
Abstract
| We present a very simple algorithm for the Least Common Ancestor
problem. We thus dispel the frequently held notion that an optimal
LCA computatio is unwieldy and unimplementable. Interestingly, this
algorithm is a sequentialisation of a previously known PRAM algorithm
of Berkman, Breslauer, Galil, Schieber and Vishkin
|
Keywords
data structures
least common ancestor
lca
range minimum query
cartesian tree
Notes
Related Papers
Bibtex
@inproceedings{ bender.farach-colton_lca00,
author = "Michael A. Bender and Martin Farach-Colton",
title = "The {LCA} Problem Revisited",
booktitle = "Latin American Theoretical {INformatics}",
pages = "88-94",
year = "2000",
url = "citeseer.nj.nec.com/346677.html" }