A POLYNOMIAL-TIME ALGORITHM FOR THE PERFECT PHYLOGENY PROBLEM WHEN THE NUMBER OF CHARACTER STATES IS FIXED

Authors
AGARWALA R FERNANDEZBACA D
Citation
R. Agarwala et D. Fernandezbaca, A POLYNOMIAL-TIME ALGORITHM FOR THE PERFECT PHYLOGENY PROBLEM WHEN THE NUMBER OF CHARACTER STATES IS FIXED, SIAM journal on computing, 23(6), 1994, pp. 1216-1224
Citations number
20
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
23
Issue
6
Year of publication
1994
Pages
1216 - 1224
Database
ISI
SICI code
0097-5397(1994)23:6<1216:APAFTP>2.0.ZU;2-P
Abstract
This paper presents a polynomial-time algorithm for determining whethe r a set of species, described by the characters they exhibit, has a pe rfect phylogeny, assuming the maximum number of possible states for a character is fixed. This solves a longstanding open problem. This resu lt should be contrasted with the proof by Steel [J. Classification 9(1 992), pp.91-116] and Bodlaender, Fellows, and Warnow [Proceedings of t he 19th International Colloquium on Automata, Languages, and Programmi ng, Lecture Notes in Computer Science, 1992. pp.273-283] that the perf ect phylogeny problem is NP complete in general.