A simple linear time algorithm for triangulating three-colored graphs

Hans Bodlaender; Ton Kloks

doi:10.1007/3-540-55210-3_201

A simple linear time algorithm for triangulating three-colored graphs

Research output: Chapter in Book/Report/Conference proceeding › Chapter › 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 2-trees. We also give an algorithm that solves the problem for partial 2-trees.

Original language	English
Title of host publication	STACS 92
Subtitle of host publication	9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992 Proceedings
Editors	Alain Finkel, Matthias Jantzen
Publisher	Springer
Pages	413-423
Number of pages	11
Volume	577
ISBN (Electronic)	978-3-540-46775-5
ISBN (Print)	978-3-540-55210-9
DOIs	https://doi.org/10.1007/3-540-55210-3_201
Publication status	Published - 1992

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/3-540-55210-3_201

http://dx.doi.org/10.1007/3-540-55210-3_201

Cite this

Bodlaender, H., & Kloks, T. (1992). A simple linear time algorithm for triangulating three-colored graphs. In A. Finkel, & M. Jantzen (Eds.), STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992 Proceedings (Vol. 577, pp. 413-423). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/3-540-55210-3_201

@inbook{b61f8fb666d14801a2bdeab0733da3ce,

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 2-trees. We also give an algorithm that solves the problem for partial 2-trees.",

author = "Hans Bodlaender and Ton Kloks",

year = "1992",

doi = "10.1007/3-540-55210-3_201",

language = "English",

isbn = "978-3-540-55210-9",

volume = "577",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "413--423",

editor = "Alain Finkel and Matthias Jantzen",

booktitle = "STACS 92",

}

A simple linear time algorithm for triangulating three-colored graphs. / Bodlaender, Hans; Kloks, Ton.
STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992 Proceedings. ed. / Alain Finkel; Matthias Jantzen. Vol. 577 Springer, 1992. p. 413-423 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - A simple linear time algorithm for triangulating three-colored graphs

AU - Bodlaender, Hans

AU - Kloks, Ton

PY - 1992

Y1 - 1992

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 2-trees. We also give an algorithm that solves the problem for partial 2-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 2-trees. We also give an algorithm that solves the problem for partial 2-trees.

U2 - 10.1007/3-540-55210-3_201

DO - 10.1007/3-540-55210-3_201

M3 - Chapter

SN - 978-3-540-55210-9

VL - 577

T3 - Lecture Notes in Computer Science

SP - 413

EP - 423

BT - STACS 92

A2 - Finkel, Alain

A2 - Jantzen, Matthias

PB - Springer

ER -

A simple linear time algorithm for triangulating three-colored graphs

Abstract

Publication series

Access to Document

Fingerprint

Cite this