Article ID Journal Published Year Pages File Type
418316 Discrete Applied Mathematics 2014 15 Pages PDF
Abstract

This paper considers the challenge of recognizing how the properties of a graph determine the performance of graph coloring algorithms. In particular, we examine how spectral properties of the graph make the graph coloring task easy or hard. We address the question of when an exact algorithm is likely to provide a solution in a reasonable computation time, when we are better off using a quick heuristic, and how the properties of the graph influence algorithm performance. A new methodology is introduced to visualize a collection of graphs in an instance space defined by their properties, with an optimal feature selection approach included to ensure that the instance space preserves the topology of an algorithm performance metric. In this instance space we can reveal how different algorithms perform across a variety of instance classes with various properties. We demonstrate the methodology using a sophisticated branch and bound exact algorithm, and the faster heuristic approaches of integer rounding of a linear programming relaxation of the graph coloring formulation, as well as a greedy degree-saturation heuristic. Our results demonstrate that spectral properties of the graph instances can provide useful descriptions of when each of these algorithms will provide the best solution for a given computational effort.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,