## 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(r^{k+1}k^{k+1}+nk^{2}) 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)