A correction to Brelaz's modification of Brown's coloring algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A correction to Brelaz's modification of Brown's coloring algorithm

Full text

Pdf (364 KB)

Source

Communications of the ACM archive
Volume 26 , Issue 8 (August 1983) table of contents

Pages: 595 - 597

Year of Publication: 1983

ISSN:0001-0782

Author

Jürgen Peemöller

Hochschule der Bundeswehr Hamburg, Hamburg, West Germany

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references cited by index terms

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/358161.358171 What is a DOI?

ABSTRACT

Brelaz's modification of Brown's exact coloring algorithm contains two errors as demonstrated in two examples. A correct version of the algorithm and a proof of the exactness are given. Finally, Brown's look-ahead rule is built into this algorithm.

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	Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
	2	Brown, J. R. Chromatic scheduling and the chromatic number problem. Manage. Sci. 19, 4 (Dec. 1972), I, 456-463.

CITED BY 12

	Olivier Coudert, Exact coloring of real-life graphs is easy, Proceedings of the 34th annual conference on Design automation, p.121-126, June 09-13, 1997, Anaheim, California, United States
	Darko Kirovski , Miodrag Potkonjak, Efficient coloring of a large spectrum of graphs, Proceedings of the 35th annual conference on Design automation, p.427-432, June 15-19, 1998, San Francisco, California, United States
	Francine Herrmann , Alain Hertz, Finding the chromatic number by means of critical graphs, Journal of Experimental Algorithmics (JEA), 7, p.10, 2002
	Fernando C. Gomes , Panos Pardalos , Carlos S. Oliveira , Mauricio G. C. Resende, Reactive GRASP with path relinking for channel assignment in mobile phone networks, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.60-67, July 2001, Rome, Italy
	Marek Kubale , Boguslaw Jackowski, A generalized implicit enumeration algorithm for graph coloring, Communications of the ACM, v.28 n.4, p.412-418, April 1985
	C. G. Prohazka, Bounding the Maximum Size of a Packet Radio Network, IEEE Transactions on Computers, v.37 n.10, p.1184-1190, October 1988
	Ivo Blöchliger , Nicolas Zufferey, A graph coloring heuristic using partial solutions and a reactive tabu scheme, Computers and Operations Research, v.35 n.3, p.960-975, March, 2008
	Philippe Galinier , Alain Hertz , Nicolas Zufferey, An adaptive memory algorithm for the k-coloring problem, Discrete Applied Mathematics, v.156 n.2, p.267-279, January, 2008
	Igor Dukanovic , Franz Rendl, A semidefinite programming-based heuristic for graph coloring, Discrete Applied Mathematics, v.156 n.2, p.180-189, January, 2008
	C. Desrosiers , P. Galinier , A. Hertz, Efficient algorithms for finding critical subgraphs, Discrete Applied Mathematics, v.156 n.2, p.244-266, January, 2008
	Alain Hertz , Matthieu Plumettaz , Nicolas Zufferey, Variable space search for graph coloring, Discrete Applied Mathematics, v.156 n.13, p.2551-2560, July, 2008
	Saoucene Mahfoudh , Pascale Minet, Maximization of energy efficiency in wireless ad hoc and sensor networks with SERENA, Mobile Information Systems, v.5 n.1, p.33-52, January 2009