Publication Date

3-15-1993

Technical Report Number

TR93-07a

Subjects

Mathematics of Computing

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.

Share

COinS