A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs

H. Bodlaender; T. Kloks

doi:10.1006/jagm.1993.1035

A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs

H. Bodlaender^*, T. Kloks

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

In this paper we consider the problem of determining whether a given colored graph can be triangulated, such that no edges between vertices of the same color are added. This problem originated from the perfect phylogeny problem from molecular biology and is strongly related with the problem of recognizing partial k-trees. In this paper we give a simple linear time algorithm that solves the problem when there are three colors. We do this by first giving a complete structural characterization of the class of partial two-trees.

Original language	English
Pages (from-to)	160-172
Number of pages	13
Journal	Journal of Algorithms
Volume	15
Issue number	1
DOIs	https://doi.org/10.1006/jagm.1993.1035
Publication status	Published - 1 Jul 1993

Access to Document

10.1006/jagm.1993.1035

Cite this

@article{cfdcd09a24714b36b3a3ed22f5597888,

title = "A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs",

abstract = "In this paper we consider the problem of determining whether a given colored graph can be triangulated, such that no edges between vertices of the same color are added. This problem originated from the perfect phylogeny problem from molecular biology and is strongly related with the problem of recognizing partial k-trees. In this paper we give a simple linear time algorithm that solves the problem when there are three colors. We do this by first giving a complete structural characterization of the class of partial two-trees.",

author = "H. Bodlaender and T. Kloks",

year = "1993",

month = jul,

day = "1",

doi = "10.1006/jagm.1993.1035",

language = "English",

volume = "15",

pages = "160--172",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs

AU - Bodlaender, H.

AU - Kloks, T.

PY - 1993/7/1

Y1 - 1993/7/1

N2 - In this paper we consider the problem of determining whether a given colored graph can be triangulated, such that no edges between vertices of the same color are added. This problem originated from the perfect phylogeny problem from molecular biology and is strongly related with the problem of recognizing partial k-trees. In this paper we give a simple linear time algorithm that solves the problem when there are three colors. We do this by first giving a complete structural characterization of the class of partial two-trees.

AB - In this paper we consider the problem of determining whether a given colored graph can be triangulated, such that no edges between vertices of the same color are added. This problem originated from the perfect phylogeny problem from molecular biology and is strongly related with the problem of recognizing partial k-trees. In this paper we give a simple linear time algorithm that solves the problem when there are three colors. We do this by first giving a complete structural characterization of the class of partial two-trees.

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

U2 - 10.1006/jagm.1993.1035

DO - 10.1006/jagm.1993.1035

M3 - Article

AN - SCOPUS:38249003604

SN - 0196-6774

VL - 15

SP - 160

EP - 172

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this