Abstract

A composite graph is a finite undirected graph in which a positive integer known as a chromaticity is associated with each vertex of the graph. The composite graph coloring problem (CGCP) is the problem of finding the chromatic number of a composite graph, i.e., the minimum number of colors (positive integers) required to assign a sequence of consecutive colors to each vertex of the graph in a manner such that adjacent vertices are not assigned sequences with colors in common and the sequence assigned to a vertex has the number of colors indicated by the chromaticity of the vertex. The CGCP problem is an NP-complete problem that has applications to scheduling and resource allocation problems in which the tasks to be scheduled are of unequal durations.

The pigeonhole principle gives rise to a problem reduction technique for the CGCP and a vertex ordering used in the vertex-sequentia1-with-interchange (VSI) algorithm. LFPHI. An upper bound on the chromatic number of a composite graph is obtained from the definition of a color-sequential coloring algorithm for the CGCP.

The performances of twelve heuristic coloring algorithms are compared on a variety of random composite graphs. Three VSI algorithms (LF1I, LFPHI, and LFCDI) performed superior to the other algorithms on graphs having the lower numbers of vertices and low edge densities while two color-sequential algorithms (RLF1 and RLFD1) were superior on graphs having the higher numbers of vertices and high edge densities.

Department(s)

Computer Science

Comments

This report is substantially the Ph.D. dissertation of the first author, completed December 1987.

Report Number

CSc-87-19

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1987 University of Missouri--Rolla, All rights reserved.

Publication Date

December 1987

Download

Share

 
COinS