1. SCSIT
  2. All Volumes and Issues
  3. Volume 744, 2012
  4. Parallel metaheuristics in graph coloring

Parallel metaheuristics in graph coloring

SCSIT.
2012;
Volume 744
: pp. 209 - 214
Authors: 

Z. Kokosiński

Cracow University of Technology, Department of Automatic Control and Information Technology,

Faculty of Electrical and Computer Engineering, Kraków, Poland

Наведено огляд застосувань паралельних метаевристик для вирішення проблем колоризації графів. Проблеми колоризації графів (GCP), сумарної колоризації графів (GCSP) та робастної колоризації графів (RGCP) є NP-повними і не мають поліноміаль- них алгоритмів. З цієї причини для різних варіантів основної проблеми колоризації графів розроблено багато наближених алгоритмів, ітераційних і гібридних. Останнім часом для задачі колоризації графів і подібних їй проблем були розроблені паралельні алгоритми, зокрема паралельні метаевристики, зокрема паралельний алгоритм табу пошуку (PTS), паралельний генетичний алгоритм (PGA) і паралельний алгоритм іміта- ції відпалу (PSA). В експериментальній перевірці алгоритмів використано графи зі сховищем DIMACS, а також випадкові графи. Дослідження застосування PGA для задач сумарної колоризації спричинило визначення нових верхніх і нижніх оцінок хроматичної суми і числа хроматичної суми для класу тестів з бази DIMACS, які є точні- шими від відомих теоретичних оцінок. Отримані результати підтверджують думку, що паралельні метаевристики можуть стати потужним інструментом для наближеного розв’язування задач колоризації графів у практичних застосуваннях, а також для експериментального визначення верхньої оцінки обраних параметрів важко обчислювальних графів.

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-to- compute graph parameters.

graph coloring
graph coloring sum
robust graph coloring
parallel metaheuristics
parallel iterative algorithms
chromatic sum
chromatic sum number
  1. Alba E. (Ed.) Parallel metaheuristics: a new class of algorithms, John Wiley & Sons. – 2005.
  2. Bouziri H., Jouini M. A tabu search approach for the sum coloring problem // Electronic Notes in Discrete Mathematics. – Vol. 36. – 2010. – P. 915–922.
  3. Cantú-Paz E. Efficient and accurate parallel genetic algorithms, Kluwer. – 2000.
  4. Catalyurek U., Feo J., Gebremedhin A., Halappanavar M., Pothen A. Graph coloring algorithms for multi-core and massively multithreaded architectures // Parallel Computing. – 2012. (accepted)
  5. Costa D., Hertz A. Ants can color graphs // J. of the Operational Research Society. – Vol. 48. – 1997. – P. 295–305.
  6. Chrząszcz G. Parallel evolutionary algorithm for the design of robust scheduling in power systems, M.Sc. thesis, Politechnika Krakowska. – 2009. (in Polish).
  7. Crainic T.G., Nourredine, H. Parallel meta-heuristics applications, [in: ] Alba E. (Ed.): Parallel metaheuristics: a new class of algorithms, John Wiley & Sons. – 2005.
  8. Dąbrowski J. Parallelization techniques for tabu search, Proc. 8th Int. Conference on Applied parallel computing: state of the art in scientific computing. – 2007.
  9. Dąbrowski J. Parallel immune system for graph coloring // Lecture Notes in Computer Science. – Vol. 4910. – 2008. – P. 497–505.
  10. Domagała P. : A paralel genetic algorithm for graph coloring in a diffusion model, M.Sc. thesis, Politechnika Krakowska. – 2006. (in Polish).
  11. Douiri M., El Bernoussi S. New algorithm for the sum coloring problem // Int. J. Contemp. Math. Sciences. – Vol. 6. – 2011. – No.10. – P.453 – 463.
  12. Douiri M., El Bernoussi S. A new heuristic for the sum coloring problem // Applied Math. Sciences. – Vol. 5. – 2011. – No.63 – P. 3121–3129.
  13. Douiri M., El Bernoussi S. A hybrid algorithm for the sum coloring problem, Proc. 2011 International Conference on Multimedia Computing and Systems (ICMCS), 7–9 April 2011, Ouarzazate, Marocco, P. 1–4.
  14. Douiri S.M., El Bernoussi S. An ant colony optimization for the sum coloring problem // International Journal of Applied Mathematics & Statistics. – Vol. 27. – 2011. – No.3. – P. 102–110.
  15. Douiri S.M., El Bernoussi S. An new ant colony optimization algorithm for the lower bound of sum coloring problem // Int. J. Math. Modeling and Algorithms, Springer. (DOI: 10.1007/s10852-012-9172-x).
  16. Erfani M., Ghanizadeh A., Abarghouei A.A., Sinaie S., Shamsuddin S.M. A Modified PSO method enhanced with fuzzy inference system for solving the planar graph coloring problem, WORLDCOMP’10, Proceedings of the 2010 International Conference on Artificial Intelligence, IC-AI, July 12-15, Las Vegas, Nevada, CSREA Press. –2010. – P.160 – 165.
  17. Garey R., Johnson D.S. Computers and intractability. A guide to the theory of NP-completeness, Freeman, San Francisco. – 1979.
  18. Giaro K. Task scheduling by graph coloring // Gdańsk University of Technology, Monographs. – Vol. 37. – 2003. (in Polish).
  19. Hadjikyriacou E., Samaras N., Margaritis K. An experimental evaluation of a parallel genetic algorithm using MPI, Proc. 13th Panhellenic Conference on Informatics, Corfu, Greece, Computer Society Press. – 2009. – P. 75–79.
  20. Han L., Han Z. A novel bi-objective genetic algorithm for the graph coloring problem, Int. Conf. on Computer Modeling and Simulation ICCMS’2010, January 22–24, Sanya, China, 2010, P. 3–6.
  21. Helmar A., Chiarandini M. Local search heuristic for chromatic sum, Proc. of The Metaheuristics Int Conference, MIC 2011, July 25–28, Udine, Italy.
  22. Jensen T.R., Toft B. Graph coloring problems, Wiley-Interscience. – 1995.
  23. Johnson D.S., Trick M.A. Cliques, coloring and satisfiability: Second DIMACS Implementation Challenge, DIMACS Series in Discr. Math. and Theor. Comp. Sc. – Vol. 26. – 1996.
  24. Kirsz K. Parallel tabu search algorithm in application to graph coloring problem, M.Sc. thesis, Politechnika Krakowska. – 2011. (in Polish)
  25. Kokosiński Z., Kołodziej M., Kwarciany K. Parallel genetic algorithm for graph coloring problem // Lecture Notes in Computer Science. – Vol. 3036. – 2004. –P. 217–224.
  26. Kokosiński Z., Kołodziej M., Kwarciany K. Efficient graph coloring with parallel genetic algorithms // Computing and Informatics. – Vol. 24. – 2005. – P. 123–147.
  27. Kokosiński Z., Kwarciany K. On sum coloring of graphs with parallel genetic algorithms // Lecture Notes in Computer Science. – Vol. 4431. – 2007. – P. 211–219.
  28. Kubale M. (Ed.) Discrete optimization. Models and methods for graph coloring, WNT, Warszawa. – 2002. (in Polish).
  29. Kubicka E., Schwenk A.J. An introduction to chromatic sums, Proc. 17th Annual ACM Computer Science Conf. – 1989. – P. 39–45.
  30. Li Y., Lucet C., Moukrim A., Sghiouer K. Greedy algorithms for the minimum sum coloring problem, Proc. Int. Workshop «Logistique et transports», March 22-24, Sousse, Tunisia, – 2009.
  31. Lim A., Wang F. Meta-heuristic for robust graph coloring problem, IEEE Int. Conference on Tools with Artificial Intelligence, ICTAI. – 2004.
  32.  Łukasik S., Kokosiński Z., Świętoń G. Parallel simulated annealing algorithm for graph coloring problem, Lecture Notes in Computer Science. – Vol. 4967. – 2008. – P. 229–238.
  33. Małafiejski M. Sum coloring of graphs, [in: ] Kubale M. (Ed.): Graph colorings. American Math. Society.Contemporary Mathematics. – Vol. 352. – 2004. – P.55–65.
  34. Mohamed D.S., El Bernoussi S. Max-Min ant system for the sum coloring problem, Proc. International Conference on Communications, Computing and Control Applications, CCCA 2011, March 3–5, Hammamet, Tunisia. – P. 1–4.
  35. Moukrim A., Sghiouer K., Lucet C., Li Y. Lower bounds for the minimal sum coloring problem // Electronic Notes in Discrete Mathematics. – Vol. 36. – 2010. – P. 663–670.
  36. Myszkowski P.B.: Solving scheduling problems by evolutionary algorithms for graph coloring problem, [in: ] Xhafa F., Abraham A. (Eds.) Metaheuristics for Scheduling in Industrial and Manufacturing Applications. Studies in Computational Intelligence. – Vol.128. – 2008. – P. 145– 167.
  37. Pahlavani A., Eshghi K. A hybrid algorithm of simulated annealing and tabu search for graph colouring problem // International Journal of Operational Research. – Vol. 11. – 2011. – No.2. – P. 136–159.
  38. Salari E., Ehgshi K. An ACO algorithm for the graph coloring problem // Int. J. Contemp. Math. Sciences. – Vol. 3. – 2008. – No.6. – P. 293–304.
  39. Yáñez J., Ramirez J. The robust coloring problem // European Journal of Operational Research. – Vol. 148. – 2003. – No. 3. – P. 546–558.
  40. Wu Q., Hao J.-K. An effective heuristic algorithm for sum coloring of graphs // Computers and Operations Research. – Vol. 39. – 2012. – No.7.
  41. COLOR web site, http://mat.gsia.cmu.edu/COLOR/instances.html.
  42. DIMACS ftp site, ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/. 43. COLORING 3 web site, http://mat.gsia.cmu.edu/COLORING03/.