Rate

To link to the entire object, paste this link in email, IM or document

To embed the entire object, paste this HTML in website

To link to this page, paste this link in email, IM or document

To embed this page, paste this HTML in website

A graph coloring algorithm for large scheduling problems

you wish to report:

Your comment:

Your Name:

Submit

Cancel

...

Rating
Title	A graph coloring algorithm for large scheduling problems
Author	Leighton, F.T.
SeriesTitle	Journal of Research of the National Bureau of Standards
Date	1979-11
Language	English
Keywords	Algorithm; chromatic number; color function; graph; graph coloring; heuristic; interchange; random test graphs; scheduling; time complexity.
Abstract	A new graph coloring algorithm is presented and compared to a wide variety of known algorithms. The algorithm is shown to exhibit O(n2) time behavior for most sparse graphs and thus is found to be particularly well suited for use with large-scale scheduling problems. In addition, a procedure for generating large random test graphs with known chromatic number is presented and is used to evaluate heuristically the capabilities of the algorithms discussed.
Publisher	National Bureau of Standards
ISSN	0160-1741
Volume	84
Issue	6
Page	489
Cite	J. Res. Bur. Stand., Vol. 84, No. 6, p. 489
Rights	The Journal of Research of the National Institute of Standards and Technology is a publication of the U.S. Government. The papers are in the public domain and are not subject to copyright in the United States. However, please pay special attention to the individual works to make sure there are no copyright restrictions indicated. Individual works may require securing other permissions from the original copyright holder.

Find results with:

	All
	Pages Enter page numbers or page ranges separated by commas. For example: 1,3,5-12