Fast and Simple Algorithms for Perfect Phylogeny and
Triangulating Colored Graphs
Authors: Richa Agarwala and David Fernandez-Baca
ABSTRACT
This paper presents an $O((r - n/m)^m rnm)$ algorithm for determining whether
a set of $n$ species has a perfect phylogeny, where $m$ is the number of
characters used to describe a species and $r$ is the maximum number of states
that a character can be in. The perfect phylogeny algorithm leads to an
$O((2e/k)^{k} e^2 k)$ algorithm for triangulating a $k$-colored graph having
$e$ edges.
DIMACS Home Page