Compatibility of unrooted phylogenetic trees is FPT
2006 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 351, no 3, 296-302 p.Article in journal (Refereed) Published
A collection of T-1, T-2,..., T-k of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible if there exists a tree T such that each tree T-i can be obtained from T by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Omega(n(k)) time, n being the number of leaves. Here, we present an O(nf (k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable (FPT) with respect to the number k of trees.
Place, publisher, year, edition, pages
2006. Vol. 351, no 3, 296-302 p.
IdentifiersURN: urn:nbn:se:kth:diva-15464DOI: 10.1016/j.tcs.2005.10.033ISI: 000235646800002ScopusID: 2-s2.0-32144460195OAI: oai:DiVA.org:kth-15464DiVA: diva2:333505
QC 20100525 QC 20111003. Conference: 1st International Conference on Parameterized and Exact Computation (IWPEC 2004). Bergen, NORWAY. SEP 14-17, 20042010-08-052010-08-052011-10-03Bibliographically approved