Parallel algorithm to Solve the Graph Coloring Problem (Matthew McGowan)

The included source code implements a variation of the Graph Coloring decision problem, as described in the included problem description text file. Two distinct algorithms are employed within the source code. The first is a branch-and-bound incremental coloring algorithm. The second algorithm uses cliques and maximum independent sets of graphs to assist in the search for the minimum number of colors needed to color the input graph. Multiple instances of each algorithm execute in parallel; as results are determined, the executing tasks are informed. This parallelization is accomplished through Java threads. Besides the Java source files, MS-DOS compilation and execution batch files are included to build and run the application.

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.