The LCA Problem Revisited

By Michael A. Bender, Martín Farach-Colton. Latin American Symposium on Theoretical Informatics, 2000

893 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Replacing suffix trees with enhanced suffix arrays (2004, result): “Fortunately, the preprocessing of L requires only linear time and space; see [4,21,31].”
Compressed Suffix Trees with Full Functionality (2007, methodology): “The algorithm of Bender and Farach-Colton [2] reduces the problem of computing lca to the Range Minimum Query as follows.”
Fast construction of nets in low dimensional metrics, and their applications (2004, methodology): “cess for ancestor of given x, when the level is at most 6logn levels below a given ancestor z. Again, Section 3.5 contains more information. (c) A constant time access for the lca of two vertices in T[BF00]. 2. A ε−1-WSPD W on the net-tree T, with support for fast membership queries. For each pair w”
Simple Linear Work Suffix Array Construction (2003, methodology): “Thus, if we preprocess LCP in linear time to answer range minimum queries in constant time [3,4,24], we can find the longest common prefix of any two suffixes in constant time.”