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.
Sager, Thomas J. and Lin, Shi-Jen, "A Color-Exchange Algorithm for Exact Graph Coloring" (1989). Computer Science Technical Reports. 16.
Keywords and Phrases
Algorithms; Branch-And-Bound; Chromatic Number; Graph-Coloring; NP-Complete; Scheduling
© 1989 University of Missouri--Rolla, All rights reserved.