Affordable Access

Parallel metaheuristics in graph coloring

Authors
Publisher
Видавництво Львівської політехніки
Publication Date
Keywords
  • Graph Coloring
  • Graph Coloring Sum
  • Robust Graph Coloring
  • Parallel Metaheuristics
  • Parallel Iterative Algorithms
  • Chromatic Sum
  • Chromatic Sum Number
  • колоризація графів
  • сумарна колоризація
  • робастна колоризація
  • паралельна метаевристика
  • паралельний ітераційний алгоритм
  • хроматична сума
  • число хроматичної суми

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, які є точнішими від відомих теоретичних оцінок. Отримані результати підтверджують думку, що паралельні метаевристики можуть стати потужним інструментом для наближеного розв’язування задач колоризації графів у практичних застосуваннях, а також для експериментального визначення верхньої оцінки обраних параметрів важко обчислювальних графів.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Parallel and On-Line Graph Coloring

on Journal of Algorithms Jan 01, 1997

Edge Coloring Series Parallel Graphs

on Journal of Algorithms Jan 01, 1995

Coloring permutation graphs in parallel

on Electronic Notes in Discrete M... Jan 01, 1999

Coloring planar graphs in parallel

on Journal of Algorithms Jan 01, 1987
More articles like this..