The Use of Fast Approximate Graph Coloring to Enhance Exact Parallel Algorithm Performance

Eblen, J., Rogers Jr., G. L., Phillips, C. A. and Langston, M. A.

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 neighbourhood 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.

Cite as: Eblen, J., Rogers Jr., G. L., Phillips, C. A. and Langston, M. A. (2012). The Use of Fast Approximate Graph Coloring to Enhance Exact Parallel Algorithm Performance. In Proc. Australasian Symposium on Parallel and Distributed Computing (AusPDC 2012) Melbourne, Australia. CRPIT, 127. Chen, J. and Ranjan, R. Eds., ACS. 31-32

(from crpit.com) (local if available)