The LCA problem revisited

Michael A. Bender, Martín Farach-Colton

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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 languageEnglish (US)
    Title of host publicationLATIN 2000
    Subtitle of host publicationTheoretical Informatics - 4th Latin American Symposium, Proceedings
    Number of pages7
    StatePublished - 2000
    Event4th Latin American Symposium on Theoretical Informatics, LATIN 2000 - Punta del Este, Uruguay
    Duration: Apr 10 2000Apr 14 2000

    Publication series

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


    Other4th Latin American Symposium on Theoretical Informatics, LATIN 2000
    CityPunta del Este

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Cite this