JCOL: A Java package for solving the graph coloring problem
share
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 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.
READ FULL TEXT