%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 }