Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(12)
allpairs shortest path
Close Relationships
Directed Acyclic Graph
Experimental Study
Optimal Algorithm
Range Minimum Query
Source Code
Transitive Closure
High Density
Lower Bound
Lowest Common Ancestor
Shortest Path
Subscribe
Academic
Publications
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 Farachcolton
Edit
Lowest common ancestors in trees and directed acyclic graphs
(
Citations: 52
)
BibTex

RIS

RefWorks
Download
Michael A. Bender
,
Martin Farachcolton
,
Giridhar Pemmasani
,
Steven Skiena
,
Pavel Sumazin
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 allpairsrepresentative LCA in DAGs in ~ O(n2:688) operations, provide a transitiveclosure
lower bound
for the allpairsrepresentativeLCA problem, and develop an LCAexistence algorithm that preprocesses the DAG in transitiveclosure time. We also present a suboptimal but practical O(n3) algorithm for allpairsrepresentative LCA in DAGs that uses ideas from the optimal algorithms in trees and DAGs. Our results reveal a close relationship between the LCA, allpairsshortestpath, and transitiveclosure 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 preprocessingquery 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. 7594, 2005
DOI:
10.1016/j.jalgor.2005.08.001
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.
(
www.sciencedirect.com
)
(
www.cs.sunysb.edu
)
(
web.cecs.pdx.edu
)
(
dx.doi.org
)
(
linkinghub.elsevier.com
)
(
explorer.csse.uwa.edu.au
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(37)
...A clear exposition of how this can be done can be found in [
40
]...
Ali Tofigh
,
et 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 Cardona
,
et al.
Comparison of Galled Trees
...The first application, considered in [
2
], is AllPairs 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 Shapira
,
et al.
AllPairs 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 kingdomphylumclassorderfamilygenusspecies 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 Clemente
,
et al.
Flexible taxonomic assignment of ambiguous sequencing reads
...The first constanttime 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 Yuan
,
et al.
Data Structures for Range Minimum Queries in Multidimensional Arrays
References
(30)
OnLine Algorithms for Orders
(
Citations: 5
)
Vincent Bouchitté
,
Jeanxavier Rampon
Journal:
Theoretical Computer Science  TCS
, vol. 175, no. 2, pp. 225238, 1997
Finding least common ancestors in directed acyclic graphs
(
Citations: 12
)
Michael A. Bender
,
Giridhar Pemmasani
,
Steven Skiena
,
Pavel Sumazin
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 845854, 2001
The Lowest Common Ancestor Problem on a Tree with an Unfixed Root
(
Citations: 8
)
Biingfeng Wang
,
Jiunnnan Tsai
,
Yuancheng Chuang
Journal:
Information Sciences  ISCI
, vol. 119, no. 12, pp. 125130, 1999
Efficient implementation of lattice operations
(
Citations: 132
)
Hassan AïtKaci
,
Robert S. Boyer
,
Patrick Lincoln
,
Roger Nasr
Journal:
ACM Transactions on Programming Languages and Systems  TOPLAS
, vol. 11, no. 1, pp. 115146, 1989
Dynamic LCA queries on trees
(
Citations: 58
)
Richard Cole
,
Ramesh Hariharanl
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 235244, 1999
Sort by:
Citations
(52)
Simultaneous Identification of Duplications and Lateral Gene Transfers
(
Citations: 1
)
Ali Tofigh
,
Michael T. Hallett
,
Jens Lagergren
Journal:
IEEE/ACM Transactions on Computational Biology and Bioinformatics  TCBB
, vol. 8, no. 2, pp. 517535, 2011
Comparison of Galled Trees
(
Citations: 1
)
Gabriel Cardona
,
Merce Llabres
,
Francesc Rossello
,
Gabriel Valiente
Journal:
IEEE/ACM Transactions on Computational Biology and Bioinformatics  TCBB
, vol. 8, no. 2, pp. 410427, 2011
Cacheoblivious index for approximate string matching
WingKai Hon
,
TakWah Lam
,
Rahul Shah
,
SiuLung Tam
,
Jeffrey Scott Vitter
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 29, pp. 35793588, 2011
AllPairs Bottleneck Paths in Vertex Weighted Graphs
Asaf Shapira
,
Raphael Yuster
,
Uri Zwick
Journal:
Algorithmica
, vol. 59, no. 4, pp. 621633, 2011
Flexible taxonomic assignment of ambiguous sequencing reads
José Carlos Clemente
,
Jesper Jansson
,
Gabriel Valiente
Journal:
BMC Bioinformatics
, vol. 12, no. 1, pp. 815, 2011