Algorithms in Bioinformatics


A   A   A
Sections
Home > Publications > New common ancestor problems in trees and directed acyclic graphs

Skip to content. | Skip to navigation

Document Actions

Johannes Fischer and Daniel H Huson (2010)

New common ancestor problems in trees and directed acyclic graphs

Information Processing Letters.

We derive a new generalization of lowest common ancestors (LCAs) in dags, called the lowest single common ancestor (LSCA). We show how to preprocess a static dag in linear time such that subsequent LSCA-queries can be answered in constant time. The size is linear in the number of nodes. We also consider a  fuzzy variant of LSCA that allows to compute a node that is only an LSCA of a given percentage of the query nodes. The space and construction time of our scheme for fuzzy LSCAs is linear, whereas the query time has a sub-logarithmic slow-down. This  fuzzy algorithm is also applicable to LCAs in trees, with the same complexities., citeulike-article-id = 6832032, citeulike-linkout-0 = http://dx.doi.org/10.1016/j.ipl.2010.02.014, citeulike-linkout-1 = http://linkinghub.elsevier.com/retrieve/pii/S0020019010000487

10.1016/j.ipl.2010.02.014
« June 2019 »
June
MoTuWeThFrSaSu
12
3456789
10111213141516
17181920212223
24252627282930