"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.
Gillett, Billy E.
Rigler, A. K.
Sager, Thomas J.
Wilkerson, Ralph W.
Hall, Leon M., 1946-
Ph. D. in Computer Science
University of Missouri--Rolla
xi, 229 pages
© 1993 Jeffrey W. Jenness, All rights reserved.
Dissertation - Restricted Access
Print OCLC #
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.http://merlin.lib.umsystem.edu/record=b2549809~S5
Jenness, Jeffrey W., "The difficulty of approximating the chromatic number for random composite graphs" (1993). Doctoral Dissertations. 913.
Share My Dissertation If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.