The use of fast approximate graph coloring to enhance exact parallel algorithm performance

The significance of graph coloring is considered in the context of reducing the running time of a parallel branch and bound algorithm to solve the maximum clique problem. The greedy color preprocessing algorithm produces an upper bound u on the color degree c of a vertex v. The color degree of a vertex is defined to be the chromatic number, γ, of the neighborhood subgraph of vertex v. The graph instance is reduced by removing any vertex v, such that u < k, where k is the size of the largest known clique. The use of this graph coloring is extended and used in the interleaved preprocessing step during the branching phase of the algorithm. The basic techniques introduced can be extended to other problems such as minimum vertex cover and maximum independent set. Finally, results are presented from experiments using real biological data.