Abstract
The graph coloring problem can be stated: “Given an undirected graph, using a minimal number of colors, assign each vertex a color so that if two vertices are connected by an edge then they are not assigned the same color.” Graph coloring can be used to solve scheduling problems with constraints of the form: events e and e' can not be scheduled together. Graph coloring is an NP-Complete problem. Generally large problems are solved heuristically, although some of the better heuristic algorithms use an exact graph coloring algorithm to finish coloring a graph after first reducing it heuristically to manageable size. Exact graph coloring is important both in its own right and as a component of heuristic coloring.
We present an improved exact graph coloring algorithm which runs in the mean over 20% faster than the DSATUR algorithm on some classes of random graphs. The improvement over DSATUR stems from the ability to prune the search tree by detecting in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far.
Recommended Citation
Sager, Thomas J. and Lin, Shi-Jen, "A Pruning Procedure for Exact Graph Coloring" (1989). Computer Science Technical Reports. 15.
https://scholarsmine.mst.edu/comsci_techreports/15
Department(s)
Computer Science
Keywords and Phrases
Graph-coloring, chromatic number, NP-Complete, scheduling
Report Number
CSc-89-3
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1989 University of Missouri--Rolla, All rights reserved.
Publication Date
1989
