Title :
A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed
Author :
Agarwala, Richa ; Fernandez-Baca, David
Author_Institution :
Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
Abstract :
We present a polynomial-time algorithm for determining whether a set of species, described by the characters they exhibit, has a perfect phylogeny, assuming the maximum number of possible states for a character is fixed. This solves a longstanding open problem. Our result should be contrasted with the proof by Steel and Bodlaender, Fellows, and Warnow that the perfect phylogeny problem is NP-complete in general
Keywords :
computational complexity; NP-complete; character states; perfect phylogeny problem; polynomial-time algorithm; Art; Biology computing; Computer science; Evolution (biology); History; Phylogeny; Polynomials; Steel;
Conference_Titel :
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-4370-6
DOI :
10.1109/SFCS.1993.366873
