Lowest common ancestors in trees and directed acyclic graphs

Lowest common ancestors in trees and directed acyclic graphs,10.1016/j.jalgor.2005.08.001,Journal of Algorithms,Michael A. Bender,Martin Farach-colton

Lowest common ancestors in trees and directed acyclic graphs   (Citations: 52)
BibTex | RIS | RefWorks Download
Version: We study the problem of finding lowest common ancestors (LCA) in trees and directed acyclic graphs (DAGs). Specifically, we extend the LCA problem to DAGs and study the LCA variants that arise in this general setting. We begin with a clear exposition of Berkman and Vishkin's simple optimal algorithm for LCA in trees. The ideas presented are not novel theoretical contributions, but they lay the foundation for our work on LCA problems in DAGs. We present an algorithm that finds all-pairs-representative LCA in DAGs in ~ O(n2:688) operations, provide a transitive-closure lower bound for the all-pairs-representative-LCA problem, and develop an LCA-existence algorithm that preprocesses the DAG in transitive-closure time. We also present a suboptimal but practical O(n3) algorithm for all-pairs-representative LCA in DAGs that uses ideas from the optimal algorithms in trees and DAGs. Our results reveal a close relationship between the LCA, all-pairs-shortest-path, and transitive-closure problems. We conclude the paper with a short experimental study of LCA algorithms in trees and DAGs. Our experiments and source code demonstrate the elegance of the preprocessing-query algorithms for LCA in trees. We show that for most trees the suboptimal ( n log n)-preprocessing (1) -query algorithm should be preferred, and demonstrate that our proposed O(n3) algorithm for all-
Journal: Journal of Algorithms - JAL , vol. 57, no. 2, pp. 75-94, 2005
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...A clear exposition of how this can be done can be found in [40]...

    Ali Tofighet al. Simultaneous Identification of Duplications and Lateral Gene Transfers

    • ...Recall that a lowest common ancestor (LCA) of a pair of nodes u; v in an rDAG is any common ancestor of u and v that is not a proper ancestor of any other common ancestor of them [5]...

    Gabriel Cardonaet al. Comparison of Galled Trees

    • ...The first application, considered in [2], is All-Pairs Lowest Common Ancestors in directed acyclic graphs...
    • ... and only if there is a directed path from u to v in G .I fu is an ancestor of v, then v is said to be a descendant of u in G .A lowest common ancestor (LCA) of two vertices u, v in a DAG is a vertex w that is an ancestor of both u and v, and such that no proper descendant of w is an ancestor of both u and v. Finding LCA’s for all pairs of vertices in a tree, or, more generally, in a DAG, has many interesting applications (see, e.g., [2])...

    Asaf Shapiraet al. All-Pairs Bottleneck Paths in Vertex Weighted Graphs

    • ...O(|T|)-time preprocessing of [53,54] to T so that the LCA of any pair of specified leaves from T can be obtained in O(1) time, unless the height of T is bounded by a constant (usual taxonomical classifications as kingdom-phylum-class-order-family-genus-species have height 8, and the NCBI taxonomy [55] has a few more levels to account for finer distinctions), in which case the LCA of any pair of specified leaves from T can readily be ...

    José Carlos Clementeet al. Flexible taxonomic assignment of ambiguous sequencing reads

    • ...The first constant-time NCA solution with linear preprocessing was given by Harel and Tarjan [15], and many eorts were spent on simplifying the solution [18, 2, 4]...

    Hao Yuanet al. Data Structures for Range Minimum Queries in Multidimensional Arrays

Sort by: