Who is Who in Phylogenetic Networks

Publications of Johannes Fischer     Order by:   Type | Year

Associated keywords

compression explicit-network from-network phylogenetic-network phylogeny polynomial

2015

1 Johannes Fischer and Daniel Peters. A Practical Succinct Data Structure for Tree-Like Graphs. In WALCOM15, Vol. 8973:65-76 of LNCS, springer, 2015. Keywords: compression, from network, phylogenetic network, phylogeny.

2010

2 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."