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
BLUM, A
[J]. 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
MONIEN, B
SPECKENMEYER, E
[J]. 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
WIGDERSON, A
[J]. JOURNAL OF THE ACM, 1983, 30 (04) : 729 - 735

← 1 →