Abstract
A vertex-composite graph is a graph that can have unequal chromaticities on its vertices. Vertex-composite graph coloring or composite graph coloring involves coloring each vertex of a composite graph with consecutive colors according to the vertex's chromaticity with no two vertices adjacent to one another having the same color(s).
New heuristic algorithms including the use of the saturation degree method have been developed in this research. All eleven heuristic algorithms including Clementson and Elphick algorithms were then tested using random composite graphs with five different chromaticity distributions. The best algorithm which uses the least average colors from the experiment is the MLF1I algorithm follow very closely by the MLF2I algorithm.
Four applications, Timetabling, Job Shop Scheduling, CPU Scheduling and Network Assignment Problem, have been formulated as composite graph coloring problems and solved using heuristic composite graph coloring algorithms.
Recommended Citation
Yek, Stephen Hong Seng and Gillett, Billy E., "Composite Graph Coloring Algorithms and Applications" (1988). Computer Science Technical Reports. 91.
https://scholarsmine.mst.edu/comsci_techreports/91
Department(s)
Computer Science
Report Number
CSc-88-7
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1988 University of Missouri--Rolla, All rights reserved.
Publication Date
August 1988
Comments
This report is substantially the M.S. thesis of the first author, completed August 1988.