A collection of T1,T2,…,Tk 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 Ti 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 Ω(nk) 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.
%0 Journal Article
%1 Bryant06
%A Bryant, David
%A Lagergren, Jens
%D 2006
%J Theoret. Comput. Sci.
%K from:davidjamesbryant
%N 3
%P 296-302
%T Compatibility of unrooted phylogenetic trees in FPT
%U http://dx.doi.org/10.1016/j.tcs.2005.10.033
%V 351
%X A collection of T1,T2,…,Tk 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 Ti 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 Ω(nk) 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.
@article{Bryant06,
abstract = {A collection of T1,T2,…,Tk 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 Ti 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 Ω(nk) 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.},
added-at = {2009-05-14T12:41:45.000+0200},
author = {Bryant, David and Lagergren, Jens},
biburl = {https://www.bibsonomy.org/bibtex/22873fb9f73144d7a00545efcbd53f42d/compevol},
coden = {TCSDI},
fjournal = {Theoretical Computer Science},
interhash = {fcce2c39849beb579265ff96d6401f5c},
intrahash = {2873fb9f73144d7a00545efcbd53f42d},
issn = {0304-3975},
journal = {Theoret. Comput. Sci.},
keywords = {from:davidjamesbryant},
month = Feb,
mrclass = {68Q25 (92D15)},
mrnumber = {MR2202491 (2006j:68038)},
mrreviewer = {Wing-Kin Sung},
number = 3,
pages = {296-302},
timestamp = {2009-05-14T12:41:45.000+0200},
title = {Compatibility of unrooted phylogenetic trees in {FPT}},
url = {http://dx.doi.org/10.1016/j.tcs.2005.10.033},
volume = 351,
year = 2006
}