Graph coloring algorithms on random graphs

<p>"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes of graphs. In addition to exact algorithms, we also look at some heuristic algorithms, limit, epsilon, and branch-and-bound."--Abstract, page ii.</p>

Name thesis:degree_name

Ph. D. in Computer Science

Grantor

University of Missouri--Rolla

Year dc:date.available

2016

Author dc:creator

• Lin, Shi-Jen

• Computer Sciences

Repository record dc:identifier

https://scholarsmine.mst.edu/doctoral_dissertations/736

OAI identifier oai:identifier

oai:scholarsmine.mst.edu:doctoral_dissertations-1738