Selecting suitable solution strategies for Classes of graph coloring instances using data mining

Abstract

The Maximal Independent Set (MIS) formulation tackles the graph coloring problem (GCP) as the partitioning of vertices of a graph into a minimum number of maximal independent sets as each MIS can be assigned a unique color. Mehrotra and Trick [5] solved the MIS formulation with an exact IP approach, but they were restricted to solving smaller or easier instances. For harder instances, it might be impossible to get the optimal solution within a reasonable computation time. We develop a heuristic algorithm, hoping that we can solve these problems in more reasonable time. However, though heuristics can find a near-optimal solution extremely fast compared to the exact approaches, there is still ..