Abstract
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.
Recommended Citation
Sager, Thomas J. and Lin, Shi-Jen, "An Improved Exact Graph Coloring Algorithm" (1989). Computer Science Technical Reports. 14.
https://scholarsmine.mst.edu/comsci_techreports/14
Department(s)
Computer Science
Keywords and Phrases
Graph-Coloring; Scheduling; Chromatic Number; Complexity Of Algorithms; Heuristic Algorithms
Report Number
CSc-89-1
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
