Graph coloring algorithms on random graphs

Author

Shi-Jen Lin

Abstract

"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.

Advisor(s)

Sager, Thomas J.
Gillett, Billy E.

Committee Member(s)

Rigler, A. K.
Wilkerson, Ralph W.
Wright, Farroll T.

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Publisher

University of Missouri--Rolla

Publication Date

Summer 1989

Pagination

xiii, 213 pages

Note about bibliography

Includes bibliographical references (pages 209-212).

Rights

© 1989 Shi-Jen Lin, All rights reserved.

Document Type

Dissertation - Open Access

File Type

text

Language

English

Thesis Number

T 5923

Print OCLC #

21719440

Recommended Citation

Lin, Shi-Jen, "Graph coloring algorithms on random graphs" (1989). Doctoral Dissertations. 736.
https://scholarsmine.mst.edu/doctoral_dissertations/736