IMPROVED EDGE-COLORING ALGORITHMS FOR PLANAR GRAPHS

被引：14

作者：

CHROBAK, M

NISHIZEKI, T

机构：

[1] UNIV CALIF RIVERSIDE, DEPT MATH & COMP SCI, RIVERSIDE, CA 92521 USA

[2] TOHOKU UNIV, DEPT ELECT COMMUN, SENDAI, MIYAGI 980, JAPAN

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1990年 / 11卷 / 01期

关键词：

D O I：

10.1016/0196-6774(90)90032-A

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of edge-coloring planar graphs. It is known that a planar graph G with maximum degree Δ ≥ 8 can be colored with Δ colors. We present two algorithms which find such a coloring when Δ ≥ 9. The first one is a sequential O(n log n) time algorithm. The other one is a parallel EREW PRAM algorithm which works in time O(log3n) and uses O(n) processors. © 1990.

引用

页码：102 / 116

页数：15

共 27 条

[1] EVERY PLANAR MAP IS 4 COLORABLE [J].

APPEL, K ;

HAKEN, W .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 82 (05) :711-712

[2]

Berge C., 1973, GRAPHS HYPERGRAPHS

[3] COLORING PLANAR GRAPHS IN PARALLEL [J].

BOYAR, JF ;

KARLOFF, HJ .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1987, 8 (04) :470-479

[4] A LINEAR 5-COLORING ALGORITHM OF PLANAR GRAPHS [J].

CHIBA, N ;

NISHIZEKI, T ;

SAITO, N .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1981, 2 (04) :317-327

[5] FAST ALGORITHMS FOR EDGE-COLORING PLANAR GRAPHS [J].

CHROBAK, M ;

YUNG, MT .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1989, 10 (01) :35-51

[6] ON EDGE COLORING BIPARTITE GRAPHS [J].

COLE, R ;

HOPCROFT, J .

SIAM JOURNAL ON COMPUTING, 1982, 11 (03) :540-546

[7]

COLE R, 1986, 18TH P ANN ACM S THE, P206

[8]

Fiorini S, 1977, EDGE COLOURINGS GRAP

[9] ON LINEAR-TIME ALGORITHMS FOR 5-COLORING PLANAR GRAPHS [J].

FREDERICKSON, GN .

INFORMATION PROCESSING LETTERS, 1984, 19 (05) :219-224

[10] ALGORITHMS FOR EDGE COLORING BIPARTITE GRAPHS AND MULTIGRAPHS [J].

GABOW, HN ;

KARIV, O .

SIAM JOURNAL ON COMPUTING, 1982, 11 (01) :117-129

← 1 2 3 →