DIMACS TR: 94-51
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.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-51.ps
DIMACS Home Page