Graph coloring heuristics from investigation of smallest hard to color graphs

Show full item record

Title: Graph coloring heuristics from investigation of smallest hard to color graphs
Author: Radin, Andrew
Abstract: Vertex coloring of graphs is an NP-complete problem. No polynomial time algorithm is known to color graphs optimally. The best we can do to handle vertex coloring of graphs is to create heuristics which provide a guess as to an optimal coloring. This thesis examines a number of known vertex coloring heuristics, and compares their performance to a brute-force optimal coloring. These comparisons are made for relatively small graphs with low numbers of vertices. The behaviors of the existing heuristics is examined to aid in the creation of new heuristics. The new heuristics are compared against the existing heuristics for both all small (n < 12) and relatively large random graphs. The result of this thesis is two new graph coloring heuristics. The first heuristic, the so called double interchange, provides the best coloring performance of the heuristics studied for small, connected graphs. The second heuristic, the annealing interchange, provides the best coloring performance of the heuristics studied for larger, random graphs.
Record URI: http://hdl.handle.net/1850/14668
Date: 2000

Files in this item

Files Size Format View
ARadinThesis05-16-2000.pdf 1.581Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse