DocumentCode
2366883
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
fYear
1993
fDate
3-5 Nov 1993
Firstpage
140
Lastpage
147
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location
Palo Alto, CA
Print_ISBN
0-8186-4370-6
Type
conf
DOI
10.1109/SFCS.1993.366873
Filename
366873
Link To Document