DIMACS TR: 94-51

Fast and Simple Algorithms for Perfect Phylogeny and Triangulating Colored Graphs

Authors: Richa Agarwala and David Fernandez-Baca


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