TRIANGULATING 3-COLORED GRAPHS IN LINEAR TIME AND LINEAR-SPACE

被引：13

作者：

IDURY, RM

SCHAFFER, AA

机构：

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1993年 / 6卷 / 02期

关键词：

CHORDAL GRAPHS; PERFECT PHYLOGENY PROBLEM; PLANAR GRAPHS; KAPPA-TREES;

D O I：

10.1137/0406023

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Kannan and Warnow [Triangulating Three-Colored Graphs, Proc. 2nd SODA, 1991, pp. 337-343 and SIAM J. Discrete Math., 5 (1992), pp. 249-258] describe an algorithm to decide whether a three-colored graph can be triangulated so that all the edges connect vertices of different colors. This problem is motivated by a problem in evolutionary biology. Kannan and Warnow have two implementation strategies for their algorithm: one uses slightly superlinear time, while the other uses linear time but quadratic space. We note that three-colored triangulatable graphs are always planar, and we use this fact to modify Kannan and Warnow's algorithm to obtain an algorithm that uses both linear time and linear space.

引用

页码：289 / 293

页数：5

共 10 条

[1]

Aho Alfred V., 1974, DESIGN ANAL COMPUTER

[2]

BODLAENDER H, 1992, LECT NOTES COMPUT SC, V577, P415

[3]

BODLAENDER HL, 1992, RUUCS9208 UTR U DEP

[4]

Buneman P., 1974, Discrete Mathematics, V9, P205, DOI 10.1016/0012-365X(74)90002-8

[5]

Golumbic M., 1980, ALGORITHMIC GRAPH TH

[6]

KANNAN S, 1991, 2ND P ANN ACM SIAM S, P337

[7] TRIANGULATING 3-COLORED GRAPHS [J].

KANNAN, SK ;

WARNOW, TJ .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (02) :249-258

[8]

MCMORRIS FR, 1983, 4TH P ANN ACM SIAM S

[9]

NISHIZEKI T, 1988, ANN DISCRETE MATH, V32

[10]

VODLAENDER H, IN PRESS P ICALP 92

← 1 →