We present two algorithms for exact graph coloring of the vertex sequential with dynamic reordering of vertices variety. The first, W-DEG, is a straight-forward improvement on Korman’s original algorithm. The second, SWAP2, is a not so straight forward improvement on Korman’s algorithm and appears to offer the best performance of known exact graph coloring algorithms.
Sager, Thomas J. and Lin, Shi-Jen, "An Improved Exact Graph Coloring Algorithm" (1989). Computer Science Technical Reports. 14.
Keywords and Phrases
Graph-Coloring; Scheduling; Chromatic Number; Complexity Of Algorithms; Heuristic Algorithms
© 1989 University of Missouri--Rolla, All rights reserved.