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

Fingerprint

Color
Dynamic programming
Phylogeny

ASJC Scopus subject areas

  • Engineering(all)

Cite this

McMorris, F. R., Warnow, T., & Wimer, T. (1993). Triangulating vertex colored graphs. In 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.

Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM, 1993. p. 120-127.

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

McMorris, FR, Warnow, T & Wimer, T 1993, Triangulating vertex colored graphs. in 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.
McMorris FR, Warnow T, Wimer T. Triangulating vertex colored graphs. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM. 1993. p. 120-127
McMorris, F. R. ; Warnow, Tandy ; Wimer, Thomas. / Triangulating vertex colored graphs. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM, 1993. pp. 120-127
@inproceedings{7b2b50ddcd6a4909ac22de4930542d3c,
title = "Triangulating vertex colored graphs",
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.",
author = "McMorris, {F. R.} and Tandy Warnow and Thomas Wimer",
year = "1993",
language = "English (US)",
pages = "120--127",
booktitle = "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Publ by ACM",

}

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 -