The Three-state Perfect Phylogeny Problem Reduces to 2-SAT
Gusfield, Dan ; Wu, Yufeng
Commun. Inf. Syst., Tome 9 (2009) no. 1, p. 295-302 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We extend a structural result by A. Dress and M. Steel, "Convex tree realizations of partitions," Applied Math Letters, 5 (1993), pp. 3–6., to show that the three-state Perfect Phylogeny problem reduces in polynomial time to the classic 2-SAT problem. We also give a more expanded exposition of the proof of the structural result from Dress and Steel. We hope this note will encourage additional researchers to try to solve the central open question: finding simple efficient solutions to the k-state Perfect Phylogeny problem for k > 3.
Publié le : 2009-05-15
Classification:  
@article{1267712110,
     author = {Gusfield, Dan and Wu, Yufeng},
     title = {The Three-state Perfect Phylogeny Problem Reduces to 2-SAT},
     journal = {Commun. Inf. Syst.},
     volume = {9},
     number = {1},
     year = {2009},
     pages = { 295-302},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1267712110}
}

Gusfield, Dan; Wu, Yufeng. The Three-state Perfect Phylogeny Problem Reduces to 2-SAT. Commun. Inf. Syst., Tome 9 (2009) no. 1, pp.  295-302. http://gdmltest.u-ga.fr/item/1267712110/