### 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 |

### Fingerprint

### ASJC Scopus subject areas

- Engineering(all)

### Cite this

*Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 120-127). Publ by ACM.

**Triangulating vertex colored graphs.** / McMorris, F. R.; Warnow, Tandy; Wimer, Thomas.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.*Publ by ACM, pp. 120-127, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, 1/25/93.

}

TY - GEN

T1 - Triangulating vertex colored graphs

AU - McMorris, F. R.

AU - Warnow, Tandy

AU - Wimer, Thomas

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027266376&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027266376&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027266376

SP - 120

EP - 127

BT - Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

ER -