Triangulating vertex colored graphs

F. R. McMorris, Tandy Warnow, Thomas Wimer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherPubl by ACM
Pages120-127
Number of pages8
StatePublished - 1993
Externally publishedYes
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Triangulating vertex colored graphs'. Together they form a unique fingerprint.

Cite this