Abstract

The composite graph coloring problem (CGCP) is a generalization of the standard graph coloring problem (SGCP). Associated with each vertex is a positive integer called its chromaticity. The chromaticity of a vertex specifies the number of consecutive colors which must be assigned to it.

An exact algorithm for solving the CGCP is presented. The algorithm is a generalization of the vertex-sequential with dynamic reordering approach for the SGCP. It is shown that the method is as effective on composite graphs as its counterpart is on standard graphs. Let X̅(CGnp) and X̅(SGnp) denote, respectively, the mean chromatic number of a sample of random composite and standard graphs of order n and edge density p. It is demonstrated that the ratio X̅(CGnp) √X(SGnp), depends on p, but, for fixed p, is essentially constant, over the range of values of n for which the algorithms were applied.

Several new heuristic methods for efficiently approximating X(CGnp) for large values of n are presented. Of these, the CDsatur and CDsaturl1 algorithms, which are generalizations of the well known Dsatur algorithm, are shown to be very competitive with previously tested procedures.

A known method for calculating probabilistic lower bounds for X̅(SGnp) is generalized to produce such bounds for X̅(CGnp). Also, a method for estimating the value of X(SGnp), is shown to produce probabilistic upper bounds for X̅(SGnp). This procedure is then generalized to a method for calculating probabilistic upper bounds for X̅(CGnp). The resulting bounds are used to evaluate the actual effectiveness of several heuristic algorithms. It is shown that, for fixed p, although the mean absolute error of the heuristic procedures appears to increase as n is varied from 100 to 1000, the mean relative error remains reasonably constant.

Department(s)

Computer Science

Comments

This report is substantially the Ph. D. dissertation of the first author, completed May, 1990.

Report Number

CSC-90-6

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

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

Publication Date

May 1990

Download

Share

 
COinS