Abstract
DEXCH, a color-exchange exact graph coloring algorithm is presented. On many classes of graphs, DEXCH can, in the mean, find the chromatic number of a graph considerably faster than the DSATUR algorithm. The improvement over DSATUR stems from the ability to reorganize the subset of colored vertices and to detect 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. The mean improvement over DSATUR is greatest on high edge-density graphs attaining the value of 42% on random graphs of edge-density 0.7 on 64 vertices.
Recommended Citation
Sager, Thomas J. and Lin, Shi-Jen, "A Color-Exchange Algorithm for Exact Graph Coloring" (1989). Computer Science Technical Reports. 16.
https://scholarsmine.mst.edu/comsci_techreports/16
Department(s)
Computer Science
Keywords and Phrases
Algorithms; Branch-And-Bound; Chromatic Number; Graph-Coloring; NP-Complete; Scheduling
Report Number
CSc-89-4
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
