Title

The difficulty of approximating the chromatic number for random composite graphs

Author

Jeffrey W. Jenness

Abstract

"Combinatorial Optimization is an important class of techniques for solving Combinatorial Problems. Many practical problems are Combinatorial Problems, such as the Traveling Salesman Problem (TSP) and Composite Graph Coloring Problem (CGCP). Unfortunately, both of these problems are 𝒩P-complete and it is not known if efficient algorithms exist to solve these problems. Even approximation with guaranteed results can be just as difficult. Recently, many generalized search techniques have been developed to improve upon the solutions found by the heuristic algorithms.

This paper presents results for CGCP. In particular, exact and heuristic algorithms are presented and analyzed. This study is made, to show empirically that CGCP cannot provide guarantees on the approximation using these heuristic methods. In addition, an improvement is presented on the interchange method by Clementson and Elphick that is used with vertex sequential algorithms. This improvement allows graphs of up to 1000 vertices to be colored in considerably less time than previous studies. The study also shows that CDSaturI heuristic does not compete as well with CDSatur as expected for large graphs with edge density of 0.2.

Several 𝒩P-completeness theorems are presented and proved. Approximation of CGCP is shown to be as difficult as finding exact solutions if we expect the approximate solutions to fall within a specified bound. These bounds on approximate solutions are shown to be directly related to the bounds that have been proved to exist for the Standard Graph Coloring Problem (SGCP).

Finally, a model of CGCP is developed so that the Tabu Search technique can be applied. Several neighborhoods are developed and tested on 50 and 100 vertex graphs. Timing and performance is analyzed against the heuristics in the previous study. Instances of larger order graphs are used to test the best neighborhood searches with Tabu Search"--Abstract, page iii.

Advisor(s)

Gillett, Billy E.

Committee Member(s)

Rigler, A. K.
Sager, Thomas J.
Wilkerson, Ralph W.
Hall, Leon M., 1946-

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

Fall 1993

Pagination

xi, 229 pages

Note about bibliography

Includes bibliographical references (pages 114-116).

Rights

© 1993 Jeffrey W. Jenness, All rights reserved.

Document Type

Dissertation - Restricted Access

File Type

text

Language

English

Thesis Number

T 6655

Print OCLC #

31067349

Link to Catalog Record

Electronic access to the full-text of this document is restricted to Missouri S&T users. Otherwise, request this publication directly from Missouri S&T Library or contact your local library.

Recommended Citation

Jenness, Jeffrey W., "The difficulty of approximating the chromatic number for random composite graphs" (1993). Doctoral Dissertations. 913.
https://scholarsmine.mst.edu/doctoral_dissertations/913