The design, analysis, and implementation of parallel simulated annealing and parallel genetic algorithms for the composite graph coloring problem

Author

Brent S. Elmer

Abstract

"The composite graph coloring problem (CGCP) is similar to the standard graph coloring problem (SGCP). Associated with each vertex of a composite graph is a positive integer which represents the chromaticity of that vertex. This number is the number of consecutive integers (colors) which must be assigned to the vertex. The goal of the CGCP is to color the graph with as few colors as possible. The largest integer used in the coloring is called the chromatic number of the graph. The CGCP is proven to be NP-complete.

Exact, heuristic, and stochastic methods are analyzed and compared. Exact methods are limited to small graphs and heuristic methods are lacking in quality. Two stochastic methods, genetic algorithms and simulated annealing, are applied to the CGCP. Both methods are implemented for MIMD parallel computers. To aid in finding the best parameter settings for the two stochastic methods, a least squares parameter optimization method is presented.

The two stochastic methods use the same solution space setup where each point in the solution space is represented by a list of the vertices of the graph in some order. Solutions to the CGCP are given by coloring the graph using these orders of the vertices in the basic-vertex-sequential algorithm. It is proven that the optimal solution is given by coloring the graph with the basic-vertex-sequential algorithm with some order of the vertices. Both stochastic methods only generate feasible solutions when searching the solution space for the optimal order of the vertices.

The stochastic methods perform superior to the heuristic methods for random graphs of fifty and one-hundred vertices. Testing on larger graphs was limited because of the amount of parallel computing resources available. It is believed that given a sufficient amount of computing time, the stochastic methods would be superior for all graph sizes"--Abstract, page iv.

Advisor(s)

Gillett, Billy E.

Committee Member(s)

Erçal, Fikret
McMillin, Bruce M.
Prater, John Bruce, 1932-2002
Bain, Lee J., 1939-

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Comments

A report which is substantially this dissertation is available here for download.

Publisher

University of Missouri--Rolla

Publication Date

Spring 1993

Journal article titles appearing in thesis/dissertation

• Analysis of parallel genetic, parallel simulated annealing, and heuristic algorithms for the composite graph coloring problem
• A parallel genetic algorithm for the composite graph coloring problem
• A parallel simulated annealing algorithm for the composite graph coloring problem

Pagination

xii, 211 pages

Note about bibliography

Includes bibliographical references.

Rights

© 1993 Brent S. Elmer, All rights reserved.

Document Type

Dissertation - Restricted Access

File Type

text

Language

English

Thesis Number

T 6539

Print OCLC #

29714569

Recommended Citation

Elmer, Brent S., "The design, analysis, and implementation of parallel simulated annealing and parallel genetic algorithms for the composite graph coloring problem" (1993). Doctoral Dissertations. 842.
https://scholarsmine.mst.edu/doctoral_dissertations/842