A Polynomial-Time Algorithm for the Phylogeny Problem when the Number of Character States is Fixed
Date
1993-03-15
Authors
Agarwala, Richa
Fernández-Baca, David
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract
We present a polynomial-time algorithm for determining whether a set of species, described by the characters they exhibit, has a phylogenetic tree, assuming the maximum number of possible states for a character ix fixed. This solves an open problem posed by Kannan and Warnow. Our result should be contrasted with the proof by Steel and Bodlænder, Fellows, and Warnow that the phylogeny problem is NP-complete in general.