The LCA problem revisited

被引：485

作者：

Bender, MA ^{[1
]}

Farach-Colton, M

机构：

[1] SUNY Stony Brook, Dept Comp Sci, Stony Brook, NY 11794 USA

[2] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08855 USA

来源：

LATIN 2000: THEORETICAL INFORMATICS | 2000年 / 1776卷

关键词：

D O I：

10.1007/10719839_9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a very simple algorithm for the Least Common Ancestors problem. We thus dispel the frequently held notion that optimal LCA computation is unwieldy and unimplementable. Interestingly, this algorithm is a sequentialization of a previously known PRAM algorithm.

引用

页码：88 / 94

页数：7