Parallel algorithm to Solve the Graph Coloring Problem (Bradley Kuszmaul)

The included source code implements a variation of the Graph Coloring decision problem, as described in the included problem description text file. The algorithm implemented searches a “Zykov tree”, which computes the chromatic number of a graph by a recursive recurrence relation (as shown in the write-up). Each subexpression in the relation can be used to find a graph coloring of modified graphs. The concept of vertices that dominate other vertices in the graph helps drives the search through the recurrence relation. The parallelization was done with Cilk++. The code was intended for Linux OS and includes a makefile to build the applications.

DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

There are downloads available under the Creative Commons License license. Download Now

Include in RSS: 

For more complete information about compiler optimizations, see our Optimization Notice.