Parallel metaheuristics in graph coloring

Abstract

In this survey paper applications of parallel metaheuristics to solving graph coloring problems are described. The Graph Coloring Problem (GCP), Graph Coloring Sum Problem (GCSP) and Robust Graph Coloring Problem (RGCP) are known to be NP-complete. They do not have any polynomial algorithms. Therefore, a number of approximation, iterative and hybrid algorithms was developed for their solving. Recently a number of parallel algorithms was proposed for GCP and related coloring problems, including parallel metaheuristics like Parallel Genetic Algorithm (PGA), Parallel Tabu Search (PTS), Parallel Simulated Annealing (PSA) etc. DIMACS benchmarks as well as random graphs were used for their experimental verification. The results obtained for GCSP contributed to finding better lower and upper bounds on chromatic sum and chromatic sum number ьfor many DIMACS graph instances, outperforming results known from the literature. The reported data support a conclusion, that parallel metaheuristics can be used efficiently for approximate solving of many graph coloring problems and for finding better upper bounds of many hard-tocompute graph parameters. Наведено огляд застосувань паралельних метаевристик для вирішення проблем колоризації графів. Проблеми колоризації графів (GCP), сумарної колоризації графів (GCSP) та робастної колоризації графів (RGCP) є NP-повними і не мають поліноміаль- них алгоритмів. З цієї причини для різних варіантів основної проблеми колоризації графів розроблено багато наближених алгоритмів, ітераційних і гібридних. Останнім часом для задачі колоризації графів і подібних їй проблем були розроблені паралельні алгоритми, зокрема паралельні метаевристики, зокрема паралельний алгоритм табу пошуку (PTS), паралельний генетичний алгоритм (PGA) і паралельний алгоритм іміта- ції відпалу (PSA). В експериментальній перевірці алгоритмів використано графи зі сховищем DIMACS, а також випадкові графи. Дослідження застосування PGA для задач сумарної колоризації спричинило визначення нових верхніх і нижніх оцінок хроматичної суми і числа хроматичної суми для класу тестів з бази DIMACS, які є точнішими від відомих теоретичних оцінок. Отримані результати підтверджують думку, що паралельні метаевристики можуть стати потужним інструментом для наближеного розв’язування задач колоризації графів у практичних застосуваннях, а також для експериментального визначення верхньої оцінки обраних параметрів важко обчислювальних графів.