JCOL: A Java package for solving the graph coloring problem

Code

• github.com/shah314/graphcoloring
  In papernone★ 6

Abstract

The graph coloring problem aims at assigning colors to the nodes of a graph such that no two connected nodes have the same color. The graph coloring problem is NP-complete and one of the harder problems to solve. Here we present a randomized heuristic to solve this problem using three cascaded algorithms. The graph coloring problem was one of Karp’s 21 NP-complete problems, and is also know as the problem of finding the chromatic number of a graph. Several other problems reduce to graph coloring including solving generalized Sudoku puzzles.

Reproductions