Evaluation of metaheuristics for robust graph coloring problem

In this paper a new formulation of the robust graph coloring problem (RGCP) is proposed. In opposition to classical GCP defined for the given graph G(V,E) not only elements of E but also E can be subject of color conflicts in edge vertices. Conflicts in E are assigned penalties 0<;P(e)<;1. In addition to satisfying constraints related to the number of colors and/or a threshold of the acceptable sum of penalties for color conflicts in graph complementary edges (rigidity level), a new bound called the relative robustness threshold (RRT) is proposed. Then two metaheuristics - SA, TS and their parallel analogues PSA and PTS - for that version of RGCP are presented and experimentally compared. For comparison we use DIMACS graph coloring instances in which a selected percentage of graph edges E is randomly moved to E. Since graph densities and chromatic numbers of DIMACS GCP instances are known in advance, the RGCP instances generated on their basis are more suitable for testing algorithms than totally random instances used so far. The results of the conducted experiments are presented and discussed.