 
Johannes Fischer and
Daniel H. Huson. New Common Ancestor Problems in Trees and Directed Acyclic Graphs. In IPL, Vol. 110(8-9):331-335, 2010.
Keywords: explicit network, phylogenetic network, polynomial.
Note: http://www-ab.informatik.uni-tuebingen.de/people/fischer/lsa.pdf.
Toggle abstract
"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. © 2010 Elsevier B.V. All rights reserved."
@Article{FischerHuson2010,
AUTHOR = {Fischer, Johannes and Huson, Daniel H.},
TITLE = {New Common Ancestor Problems in Trees and Directed Acyclic Graphs},
YEAR = {2010},
JOURNAL = {IPL},
VOLUME = {110},
NUMBER = {8-9},
PAGES = {331-335},
URL = {http://dx.doi.org/10.1016/j.ipl.2010.02.014},
NOTE = { http://www-ab.informatik.uni-tuebingen.de/people/fischer/lsa.pdf},
KEYWORDS = {explicit network, phylogenetic network, polynomial} } |
- forked on GitHub.