Abstract
We are interested in the class of vertex colored graphs which can be triangulated without the introduction of edges between vertices of the same color. This is related to a fundamental and longstanding problem for numerical taxonomists, called the Perfect Phylogeny problem. These problems are known to be polynomially equivalent and NP-Complete. In this paper we present a dynamic programming algorithm which can be used to determine whether a given vertex colored graph can be so triangulated, and which runs in O((n+m(k-2))k+1) time, where the graph has n vertices, m edges, and k colors. The corresponding algorithm for the Perfect Phylogeny Problem runs in O(rk+1kk+1+nk2) time, where n species are defined by k characters each having r states.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
Publisher | Publ by ACM |
Pages | 120-127 |
Number of pages | 8 |
State | Published - 1993 |
Externally published | Yes |
Event | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993 |
Other
Other | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
City | Austin, TX, USA |
Period | 1/25/93 → 1/27/93 |
ASJC Scopus subject areas
- Engineering(all)