Computational graph theory
Craig C. Douglas, Michael Sollami · 2013
The applications of graph theory to the development of approximation algorithms for NP-complete combinatorial decision problems are of particular importance in computer science. In this dissertation, we present new heuristics-based algorithms for the approximability of certain computational problems in chromatic graph theory. Both population-based and local search strategies are applied to such problems as minimum vertex and edge colorings, both of which are relevant to compiler optimization. Edge colorings of cubic graphs in particular have attracted much attention because of the Four-Color Problem and the Cycle Double Cover Conjecture. Portions of the research presented descend from the Trick program: the systematic implementation and profiling of various theoretical algorithms on networks; however the treatment of the Vertex and Edge Coloring Problems and the computational testing of graph theoretic conjectures are the primary focus. The necessary preliminaries concerning graph theory, algorithms, and computational complexity theory are here presented alongside the discovery of a new rare class of Snark graphs. Novel graph-drawing algorithms are presented to test longstanding conjectures in chromatic graph theory, such as Hadwigger-Nelson. Competitive algorithms for computing graph and hypergraph invariants are described and then used to compute new bounds on parameterized graph distributions. Methods from nonlinear optimization, including population-based, meta-heuristic, and probabilistic techniques, are used in formulating new evolutionary methods for coloring algorithms. Finally, we summarize the results obtained from systematic experiments on DIMACS Computational Challenge graphs.