Forging optimal solutions to the edge-coloring problem
Brandon P. Enochs, Roger L. Wainwright · 2001
The applications of a modified version of the simulated annealing algorithm for solving the edge-coloring problem, which consists of partitioning the edges of a graph into the minimum number of disjoint subsets such that no two edges in a given subset are adjacent, was investigated. With the exception of coloring bipartite graphs, finding a minimum edge coloring of a graph is NP-Complete. The traditional simulated annealing algorithm was modified to incorporate an additional perturbation (disruptive) operator. The details of the modifications to the simulated annealing algorithm, and the technique we chose to represent solutions for the edge-coloring problem are presented in the paper. We also describe two perturbation operators used by our modified technique, along with the heuristic function used to evaluate solutions. Our algorithm for solving the edge-coloring problem was tested on over sixty test graphs from the literature. In every case, our algorithm found the optimal edge coloring. We compared our algorithm to a grouping genetic algorithm technique for solving this problem published recently in the literature. Our results over a wide variety of test graphs were vastly superior to the grouping genetic algorithm technique.