The LCA problem revisited

Michael A. Bender; Martín Farach-Colton

doi:10.1007/10719839_9

The LCA problem revisited

Michael A. Bender, Martín Farach-Colton

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	LATIN 2000
Subtitle of host publication	Theoretical Informatics - 4th Latin American Symposium, Proceedings
Pages	88-94
Number of pages	7
DOIs	https://doi.org/10.1007/10719839_9
State	Published - 2000
Event	4th Latin American Symposium on Theoretical Informatics, LATIN 2000 - Punta del Este, Uruguay Duration: Apr 10 2000 → Apr 14 2000

Publication series

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

Other

Other	4th Latin American Symposium on Theoretical Informatics, LATIN 2000
Country/Territory	Uruguay
City	Punta del Este
Period	4/10/00 → 4/14/00

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/10719839_9

Cite this

The LCA problem revisited. / Bender, Michael A.; Farach-Colton, Martín.
LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings. 2000. p. 88-94 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1776 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bender, MA & Farach-Colton, M 2000, The LCA problem revisited. in LATIN 2000: Theoretical Informatics - 4th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1776 LNCS, pp. 88-94, 4th Latin American Symposium on Theoretical Informatics, LATIN 2000, Punta del Este, Uruguay, 4/10/00. https://doi.org/10.1007/10719839_9

@inproceedings{e76d57823ea4429e944d84f48480da1a,

title = "The LCA problem revisited",

abstract = "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.",

author = "Bender, {Michael A.} and Mart{\'i}n Farach-Colton",

year = "2000",

doi = "10.1007/10719839_9",

language = "English (US)",

isbn = "3540673067",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "88--94",

booktitle = "LATIN 2000",

note = "4th Latin American Symposium on Theoretical Informatics, LATIN 2000 ; Conference date: 10-04-2000 Through 14-04-2000",

}

TY - GEN

T1 - The LCA problem revisited

AU - Bender, Michael A.

AU - Farach-Colton, Martín

PY - 2000

Y1 - 2000

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

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

UR - http://www.scopus.com/inward/record.url?scp=84896788505&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84896788505&partnerID=8YFLogxK

U2 - 10.1007/10719839_9

DO - 10.1007/10719839_9

M3 - Conference contribution

AN - SCOPUS:84896788505

SN - 3540673067

SN - 9783540673064

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 88

EP - 94

BT - LATIN 2000

T2 - 4th Latin American Symposium on Theoretical Informatics, LATIN 2000

Y2 - 10 April 2000 through 14 April 2000

ER -

The LCA problem revisited

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this