Improving the performance guarantee for approximate graph coloring

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improving the performance guarantee for approximate graph coloring

Full text

Pdf (365 KB)

Source

Journal of the ACM (JACM) archive
Volume 30 , Issue 4 (October 1983) table of contents

Pages: 729 - 735

Year of Publication: 1983

ISSN:0004-5411

Author

Avi Wigderson

Univ. of California, Berkeley

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 124, Citation Count: 27

Additional Information:

references cited by index terms review 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/2157.2158 What is a DOI?

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.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
	3	HA~tt'f, F. Graph Theory. Reading, Mass., 1971.
	4	JOHNSON, D.S. Worst case bchavlour or graph coloring algorithms. In Proe. 3th South-Eastern Conf. on Combmatorics, Graph Theory and Computing. Utllitas Mathematica Publishing, Winnipeg, Canada, 1974, pp. 513-528.
	5	KARP, R.M. Reducabdlty among combinatorial problems. In Complexuy of Computer Computations, R.E. Miller and J.W. Thatcher, F, As. Plenum Press, New York, 1972, pp. 85-104.
	6	MA'rtn.~ D.W., MARBLE, G., Am) lssxcsoN, J D.Graph coloring algorithms. In Graph Theory and Computing, R.C. Reed, Ed., Acadermc Press, New York, 1972, pp. 109-122.
	7	Mxaxa~, D.W. Bounded color functions on graphs. Networks 2 (1972), 29-44.
	8	ROBERTS, A.W., AND VARBERG, D.E. Convex dnalysys. Academic Press, New York, London, 1973, pp. 211-2t6.
	9	Larry Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, v.5 n.3, p.19-25, July 1973 [doi>10.1145/1008293.1008294]
	10	Wm.sH, D.J.A., AND POWnL, M.B.An upper bound to the chromatic number of a graph and its application to time tabling problems. Comput. ~ 10 (1967), 85-86.
	11	WILLIAMS, M.R.The coloring of very large graphs, In Combinatorial Structures and their Applications, R. Guy, ed., Gordon and Breach, New York, 1970.
	12	Avi Wigderson, A new approximate graph coloring algorithm, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.325-329, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802207]
	13	WOOD, D.C.A technique for coloring a graph apphcable to large scale time tabling problems. Comtmt. d. 12 (1969), 317-319.

CITED BY 27

	A. Blum, An O(n^0.4)-approximation algorithm for 3-coloring, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.535-542, May 14-17, 1989, Seattle, Washington, United States
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States
	Eran Halperin , Ram Nathaniel , Uri Zwick, Coloring k-colorable graphs using smaller palettes, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.319-326, January 07-09, 2001, Washington, D.C., United States
	S. Ramanathan , Errol L. Lloyd, Scheduling algorithms for multi-hop radio networks, ACM SIGCOMM Computer Communication Review, v.22 n.4, p.211-222, Oct. 1992
	Vijay Raghavan , Jeremy Spinrad, Robust algorithms for restricted domains, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.460-467, January 07-09, 2001, Washington, D.C., United States
	David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998
	Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996
	Subramanian Ramanathan , Errol L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking (TON), v.1 n.2, p.166-177, April 1993
	Uriel Feige, Randomized graph products, chromatic numbers, and Lovasz j-function, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.635-640, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Avrim Blum, New approximation algorithms for graph coloring, Journal of the ACM (JACM), v.41 n.3, p.470-516, May 1994
	L. J. Cowen , W. Goddard , C. E. Jesurum, Coloring with defect, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 05-07, 1997, New Orleans, Louisiana, United States
	Vangelis T. Paschos, A survey of approximately optimal solutions to some covering and packing problems, ACM Computing Surveys (CSUR), v.29 n.2, p.171-209, June 1997
	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994
	V. Th. Paschos, Polynomial approximation and graph-coloring, Computing, v.70 n.1, p.41-86, March 2003
	P. J. Bernhard, Bounds on the Performance of Message Routing Heuristics, IEEE Transactions on Computers, v.42 n.10, p.1253-1256, October 1993
	Eran Halperin , Ram Nathaniel , Uri Zwick, Coloring k-colorable graphs using relatively small palettes, Journal of Algorithms, v.45 n.1, p.72-90, October 2002
	Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
	Vijay Raghavan , Jeremy Spinrad, Robust algorithms for restricted domains, Journal of Algorithms, v.48 n.1, p.160-172, August 2003
	Michael Krivelevich , Benny Sudakov, Approximate coloring of uniform hypergraphs, Journal of Algorithms, v.49 n.1, p.2-12, 1 October 2003
	Noga Alon , Pierre Kelsen , Sanjeev Mahajan , Hariharan Ramesh, Coloring 2-colorable hypergraphs with a sublinear number of colors, Nordic Journal of Computing, v.3 n.4, p.425-439, Winter 1996
	Anindo Bagchi , S. Louis Hakimi, Data Transfers in Broadcast Networks, IEEE Transactions on Computers, v.41 n.7, p.842-847, July 1992
	Sanjeev Arora , Eden Chlamtac, New approximation guarantee for chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	S. S. Ravi , D. Gu, On approximation algorithms for microcode bit minimization, Proceedings of the 21st annual workshop on Microprogramming and microarchitecture, p.67-69, November 28-December 02, 1988, San Diego, California, United States
	Elad Hazan , Shmuel Safra , Oded Schwartz, On the complexity of approximating k-set packing, Computational Complexity, v.15 n.1, p.20-39, January 2006
	Rajeev Kumar , Paresh Tolay , Siddharth Tiwary, Enhancing solution quality of the biobjective graph coloring problem using hybridization of EA: biobjective graph coloring problem, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	M. Sh. Levin, Combinatorial optimization in system configuration design, Automation and Remote Control, v.70 n.3, p.519-561, March 2009

INDEX TERMS

Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Graph algorithms

General Terms:
Algorithms, Performance, Theory

REVIEW

"William Benjamin Poucher : Reviewer"

A graph coloring algorithm makes an assignment of colors to the vertices of a graph so that each vertex is of a different color than its neighbors. The chromatic number of a graph is the least number of colors for which such an assignment can be more...

Collaborative Colleagues:

Avi Wigderson: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player