A SIMPLE LINEAR-TIME ALGORITHM FOR TRIANGULATING 3-COLORED GRAPHS

被引：16

作者：

BODLAENDER, H ^{[1
]}

KLOKS, T ^{[1
]}

机构：

[1] UNIV UTRECHT,DEPT COMP SCI,3508 TB UTRECHT,NETHERLANDS

来源：

JOURNAL OF ALGORITHMS | 1993年 / 15卷 / 01期

关键词：

D O I：

10.1006/jagm.1993.1035

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. © 1993 Academic Press, Inc.

引用

页码：160 / 172

页数：13

共 12 条

[1]

BODLAENDER HL, 1991, LECT NOTES COMPUT SC, V510, P544

[2]

BODLAENDER HL, 1986, RUUCS8622 UTR U DEP

[3]

Dirac Gabriel Andrew, 1961, ABH MATH SEM HAMBURG, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]

[4]

FELLOWS MR, 1991, COMMUNICATION

[5] INCIDENCE MATRICES AND INTERVAL GRAPHS [J].

FULKERSON, DR ;

GROSS, OA .

PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) :835-+

[6]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[7]

KANNAN S, 1992, SIAM J DISCRETE MATH, V5, P362

[8]

KLOKS T, IN PRESS ENUMERATION

[9] ALGORITHMS FINDING TREE-DECOMPOSITIONS OF GRAPHS [J].

MATOUSEK, J ;

THOMAS, R .

JOURNAL OF ALGORITHMS, 1991, 12 (01) :1-22

[10]

MCMORRIS CF, P SODA 93

← 1 2 →