Masters Theses

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"--Abstract, page ii.

Advisor(s)

Gillett, Billy E.

Committee Member(s)

Rigler, A. K.
Alptekin, Sema

Department(s)

Computer Science

Degree Name

M.S. in Computer Science

Publisher

University of Missouri--Rolla

Publication Date

Fall 1988

Pagination

viii, 98 pages

Note about bibliography

Includes bibliographical references (pages 95-97).

Rights

© 1988 Stephen Yek Hong Seng, All rights reserved.

Document Type

Thesis - Open Access

File Type

text

Language

English

Thesis Number

T 5784

Print OCLC #

19467927

Download

Share

 
COinS