JCOL - JCOL: A Java package for solving the graph coloring problem

Implementation of graph coloring heuristics like DSATUR, Iterated Greedy and Local Search. Also includes an implementation of the backtracking graph coloring algorithm.

Scientific Software - Peer-reviewed - Java
Published by shah314 almost 6 years ago

JCOL - Heuristic for Graph Coloring

Implementation of the DSatur heuristics for graph coloring in Java. The heuristic follows the following steps:

Compute a clique (maximum is good) Color the clique Sort the rest of the vertices in non-increasing order of the degree of saturation Color the vertices in the order given by 3. Also, when a vertex is colored, change the degree of saturation of the neighboring vertices so that the order of coloring changes Improve the coloring using Iterated Greedy techniques [2] Improve the coloring using min-conflicts local search Report the coloring

Scientific Software - Peer-reviewed - Java
Published by shah314 over 6 years ago