Abstract

We are interested here in the problem of determining whether we can triangulate a vertex-colored graph without introducing edges between vertices of the same color. This problem is motivated by a longstanding and fundamental problem in numerical taxonomy called the Perfect Phylogeny Problem, which is concerned with the inference of evolutionary history. This problem is also related to the problem of recognizing partial k-trees, a class of graphs that has received a lot of attention recently. In this paper we present an almost linear time algorithm for this problem in the case that the graph is three colored.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PublisherAssociation for Computing Machinery
Pages337-343
Number of pages7
ISBN (Print)0897913760
StatePublished - Mar 1 1991
Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
Duration: Jan 28 1991Jan 30 1991

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
CountryUnited States
CitySan Francisco
Period1/28/911/30/91

Fingerprint

Colored Graph
Taxonomies
Color
Numerical Taxonomy
Partial K-tree
Triangulate
Phylogeny
Linear-time Algorithm
Graph in graph theory
Vertex of a graph

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Kannan, S. K., & Warnow, T. (1991). Triangulating three-colored graphs. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 (pp. 337-343). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.

Triangulating three-colored graphs. / Kannan, Sampath K.; Warnow, Tandy.

Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, 1991. p. 337-343 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

Kannan, SK & Warnow, T 1991, Triangulating three-colored graphs. in Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 337-343, 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991, San Francisco, United States, 1/28/91.
Kannan SK, Warnow T. Triangulating three-colored graphs. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery. 1991. p. 337-343. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
Kannan, Sampath K. ; Warnow, Tandy. / Triangulating three-colored graphs. Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, 1991. pp. 337-343 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{94b464489db841ebbc396677625cd99e,
title = "Triangulating three-colored graphs",
abstract = "We are interested here in the problem of determining whether we can triangulate a vertex-colored graph without introducing edges between vertices of the same color. This problem is motivated by a longstanding and fundamental problem in numerical taxonomy called the Perfect Phylogeny Problem, which is concerned with the inference of evolutionary history. This problem is also related to the problem of recognizing partial k-trees, a class of graphs that has received a lot of attention recently. In this paper we present an almost linear time algorithm for this problem in the case that the graph is three colored.",
author = "Kannan, {Sampath K.} and Tandy Warnow",
year = "1991",
month = "3",
day = "1",
language = "English (US)",
isbn = "0897913760",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "337--343",
booktitle = "Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991",

}

TY - GEN

T1 - Triangulating three-colored graphs

AU - Kannan, Sampath K.

AU - Warnow, Tandy

PY - 1991/3/1

Y1 - 1991/3/1

N2 - We are interested here in the problem of determining whether we can triangulate a vertex-colored graph without introducing edges between vertices of the same color. This problem is motivated by a longstanding and fundamental problem in numerical taxonomy called the Perfect Phylogeny Problem, which is concerned with the inference of evolutionary history. This problem is also related to the problem of recognizing partial k-trees, a class of graphs that has received a lot of attention recently. In this paper we present an almost linear time algorithm for this problem in the case that the graph is three colored.

AB - We are interested here in the problem of determining whether we can triangulate a vertex-colored graph without introducing edges between vertices of the same color. This problem is motivated by a longstanding and fundamental problem in numerical taxonomy called the Perfect Phylogeny Problem, which is concerned with the inference of evolutionary history. This problem is also related to the problem of recognizing partial k-trees, a class of graphs that has received a lot of attention recently. In this paper we present an almost linear time algorithm for this problem in the case that the graph is three colored.

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

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

M3 - Conference contribution

AN - SCOPUS:70350774134

SN - 0897913760

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 337

EP - 343

BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

PB - Association for Computing Machinery

ER -