An (O)over-tilda(n(3/14))-coloring algorithm for 3-colorable graphs

被引：72

作者：

Blum, A ^{[1
]}

Karger, D ^{[1
]}

机构：

[1] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

来源：

INFORMATION PROCESSING LETTERS | 1997年 / 61卷 / 01期

关键词：

graph coloring; approximation algorithms; analysis of algorithms;

D O I：

10.1016/S0020-0190(96)00190-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show how the results of Karger, Motwani, and Sudan (1994) and Blum (1994) can be combined in a natural manner to yield a polynomial-time algorithm for (O) over tilde(n(3/14))-coloring any n-node 3-colorable graph. This improves on the previous best bound of (O) over tilde(n(1/4)) colors (Karger et al., 1994).

引用

页码：49 / 53

页数：5

共 9 条

[1]

Bar-Yehuda R., 1985, ANN DISCRETE MATH, V25, P27, DOI DOI 10.1016/S0304-0208(08)73101-3

[2]

Bellare M., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P184, DOI 10.1145/195058.195129

[3]

Blum A., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P535, DOI 10.1145/73007.73058

[4] NEW APPROXIMATION ALGORITHMS FOR GRAPH-COLORING [J].

BLUM, A .

JOURNAL OF THE ACM, 1994, 41 (03) :470-516

[5]

KARGER DR, 1994, P 35 ANN S FDN COMP

[6]

KHANNA S, 1992, P 2 ISR S THEOR COMP, P250

[7] RAMSEY NUMBERS AND AN APPROXIMATION ALGORITHM FOR THE VERTEX COVER PROBLEM [J].

MONIEN, B ;

SPECKENMEYER, E .

ACTA INFORMATICA, 1985, 22 (01) :115-123

[8]

Schiermeyer I, 1995, LECT NOTES COMPUT SC, V1017, P146

[9] IMPROVING THE PERFORMANCE GUARANTEE FOR APPROXIMATE GRAPH-COLORING [J].

WIGDERSON, A .

JOURNAL OF THE ACM, 1983, 30 (04) :729-735

← 1 →