An O(n0.4)-approximation algorithm for 3-coloring

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(n^0.4)-approximation algorithm for 3-coloring

Full text

Pdf (818 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-first annual ACM symposium on Theory of computing table of contents

Seattle, Washington, United States

Pages: 535 - 542

Year of Publication: 1989

ISBN:0-89791-307-8

Author

A. Blum

MIT Laboratory for Computer Science, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 21, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/73007.73058 What is a DOI?

ABSTRACT

This paper presents a polynomial-time algorithm to color any 3-colorable n-node graph with O(n2/5 log8/5 n) colors, improving the best previously known bound of O(√n/√logn) colors. By reducing the number of colors needed to color a 3-colorable graph, the algorithm also improves the bound for k-coloring for fixed k ≥ 3 from the previous O((n/log n)1-1/(k-1)) colors to O(n1-1/(k-4/3) log8/5 n) colors. An extension of the algorithm further improves the bounds. Precise values appear in a table at the end of this paper.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BE	Bar-Yehuda, R and S Even "A 2-l~ l--a!e~ Performance Ratio for the W,~ighted Vertex (:over Problem", Technion Haifa, Technical Report 260, January 1983.
	BR	Berger, B. and J. Rompel, "A Better Performance Guarantee for Approximate Graph Coloring'', Algorithmica (to appear).
	LSW	Linial, N., M. Saks and A. Wigderson, Personal communication.
	LV	Linial, N. and U. Vazirani, "x(G2) and Approximations for Chromatic Number", to appear.
	MS	Burkhard Monien , Ewald Speckenmeyer, Ramsey numbers and an approximation algorithm for the vertex cover problem, Acta Informatica, v.22 n.1, p.115-123, April 1985 [doi>10.1007/BF00290149]
	R	Raghavan, P., Personal communication.
	W	Avi Wigderson, Improving the performance guarantee for approximate graph coloring, Journal of the ACM (JACM), v.30 n.4, p.729-735, Oct. 1983 [doi>10.1145/2157.2158]

CITED BY 4

	Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994
	Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994
	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States
	A. E. Eiben , J. K. Van Der Hauw , J. I. Van Hemert, Graph Coloring with Adaptive Evolutionary Algorithms, Journal of Heuristics, v.4 n.1, p.25-46, June 1998