Geodesic
The agreement problem for unrooted phylogenetic trees is FPT
Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 385-392.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A collection T of k unrooted phylogenetic trees on different leaf sets is said to be strictly compatible or in agreement if there exists a tree T such that each tree in T can be obtained from T by deleting leaves and suppressing degree-2 vertices. The problem of determining if a set of unrooted trees is in agreement has been proved NP-hard in 1992. Here, we show that an f(k) ·n algorithm exists, for some computable function f of k, proving that strict compatibility of unrooted phylogenetic trees is fixed-parameter tractable with respect to the number k of trees. Designing a practical FPT algorithm remains an open problem. 
@article{JGAA_2014_18_3_a3,
     author = {Celine Scornavacca and Leo van Iersel and Steven Kelk and David Bryant},
     title = {The agreement problem for unrooted phylogenetic trees is {FPT}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {385--392},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2014},
     doi = {10.7155/jgaa.00327},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00327/}
}
TY  - JOUR
AU  - Celine Scornavacca
AU  - Leo van Iersel
AU  - Steven Kelk
AU  - David Bryant
TI  - The agreement problem for unrooted phylogenetic trees is FPT
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 385
EP  - 392
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00327/
DO  - 10.7155/jgaa.00327
LA  - en
ID  - JGAA_2014_18_3_a3
ER  - 
%0 Journal Article
%A Celine Scornavacca
%A Leo van Iersel
%A Steven Kelk
%A David Bryant
%T The agreement problem for unrooted phylogenetic trees is FPT
%J Journal of Graph Algorithms and Applications
%D 2014
%P 385-392
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00327/
%R 10.7155/jgaa.00327
%G en
%F JGAA_2014_18_3_a3
Celine Scornavacca; Leo van Iersel; Steven Kelk; David Bryant. The agreement problem for unrooted phylogenetic trees is FPT. Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 385-392. doi : 10.7155/jgaa.00327. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00327/

Cité par Sources :