The LCA Problem Revisited Export

@inproceedings{citeulike:4631, abstract = {We present a very simple algorithm for the Least Common Ancestor problem. We thus dispel the frequently held notion that an optimal LCA computation is unwieldy and unimplementable. Interestingly, this algorithm is a sequentialization of a previously known PRAM algorithm of Berkman, Breslauer, Galil, Schieber, and Vishkin [1]. Keywords: Data Structures, Least Common Ancestor (LCA), Range Minimum Query (RMQ), Cartesian Tree. 1 Introduction One of the most fundamental algorithmic problems on trees ...}, author = {Bender, Michael A. and Farach-Colton, Martin}, booktitle = {Latin American Theoretical INformatics}, citeulike-article-id = {4631}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.6179}, keywords = {algorithms, data-structures, least-common-ancestor}, pages = {88--94}, posted-at = {2004-12-23 02:20:01}, title = {The LCA Problem Revisited}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.6179}, year = {2000} }

TY - CONF ID - citeulike:4631 L3 - citeulike-article-id:4631 N2 - We present a very simple algorithm for the Least Common Ancestor problem. We thus dispel the frequently held notion that an optimal LCA computation is unwieldy and unimplementable. Interestingly, this algorithm is a sequentialization of a previously known PRAM algorithm of Berkman, Breslauer, Galil, Schieber, and Vishkin [1]. Keywords: Data Structures, Least Common Ancestor (LCA), Range Minimum Query (RMQ), Cartesian Tree. 1 Introduction One of the most fundamental algorithmic problems on trees ... EP - 94 TI - The LCA Problem Revisited T2 - Latin American Theoretical INformatics SP - 88 KW - algorithms KW - data-structures KW - least-common-ancestor AU - Bender, Michael AU - Farach-Colton, Martin PY - 2000/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.6179 ER -