The difficulty of approximating the chromatic number for random composite graphs

<p>"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.</p> <p>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.</p> <p>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).</p> <p>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.</p>

Name thesis:degree_name

Ph. D. in Computer Science

Grantor

University of Missouri--Rolla

Year dc:date.available

2016

Author dc:creator

• Jenness, Jeffrey W.

• Computer Sciences

Repository record dc:identifier

https://scholarsmine.mst.edu/doctoral_dissertations/913

OAI identifier oai:identifier

oai:scholarsmine.mst.edu:doctoral_dissertations-1915