Evaluation of Metaheuristics for Robust Graph Coloring Problem
Zbigniew Kokosinski, Łukasz Ochał
DOI: http://dx.doi.org/10.15439/2015F293
Citation: Proceedings of the 2015 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 5, pages 519–524 (2015)
Abstract. 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 Ē can be subject of color conflicts in edge vertices. Conflicts in Ē 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 and 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 Ē. 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 then totally random instances used so far. The results of the conducted experiments are presented and discussed.