Genetic algorithm for black and white coloring problem on graphs

Authors

  • Luis Eduardo Urván Rivero Posgrado en optimización UAM Azcapotzalco
  • Javier Ramírez Rodríguez Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México.
  • Rafael López Bracho Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México

DOI:

https://doi.org/10.30973/progmat/2018.10.1/3

Keywords:

Anticoloring, Genetic Algorithm, BWC

Abstract

A classical problem in graph theory and combinatorial optimization is the known as Graph Coloring Problem (GC). This problem consists in assigning colors to vertices of a graph such that two adjacent vertices must have different colors. The objective in this problem is to find the minimum number of colors needed to coloring the graph under the coloring condition. In the case of the Graph Anti-Coloring Problem (GAC) the color assignment is opposite. In this case two adjacent vertices must have the same color or one of them does not have any color. In this problem the objective is different in the sense of number of colors which is fixed. This problem can be turned in an optimization problem. The GAC is NP-Complete, even with two colors[2]. In this work we deal with two colors special case of GAC with genetic algorithms and compare with Tabú Search which is the state of the art solution for this problem[3].

Author Biographies

Luis Eduardo Urván Rivero, Posgrado en optimización UAM Azcapotzalco

Ingeniero en computación por la Universidad Autónoma Metropolitana (UAM) Azcapotzalco, Maestro en optimización y Candidato a Doctor en Optimización por la misma Institución.

Javier Ramírez Rodríguez, Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México.

Actuario por la Universidad Nacional Autónoma de México y Doctor en Ciencias Matemáticas por la Universidad Complutense de Madrid, España. Actualmente se desempeña como profesor investigador en el Departamento de Sistemas de la UAM Azcapotzalco.

Rafael López Bracho, Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México

Actuario por la Universidad Nacional Autónoma de México, tiene un Diplome d’études approfondies en investigación de operaciones por la Université Scientifique et Medicale de Grenoble, Francia y Doctor en Informática por la Université de Paris Sud, Francia en el año 1981. Actualmente se desempeña como profesor investigador en el Departamento de Sistemas de la UAM Azcapotzalco.

References

Bäck, T., Schütz, M. Intelligent mutation rate control in canonical genetic algorithms. Foundations of Intelligent Systems. 1996, 158–167. https://doi.org/10.1007/3-540-61286-6_141

Berend, D., Korach, E., Zucker, S. A Reduction of the anticoloring problem to connected graphs. Electronic Notes in Discrete Mathematics. 2007, 28 445– 451. https://doi.org/10.1016/j.endm.2007.01.062

Berend, D., Korach, E., Zucker, S. Tabú search for the BWC problem. Journal of Global Optimization. 2012, 54 (4), 649–667. https://doi.org/10.1007/s10898-011-9783-1

Berge, C., Minieka, E. Graphs and hypergraphs. North-Holland publishing company Amsterdam.

Holland, J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press.

Lipton, R.J., Tarjan, R.E. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics. 1979, 36 (2), 177–189. https://doi.org/10.1137/0136016

López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Stützle, T., Birattari, M. The irace package: Iterated Racing for Automatic Algorithm Configuration. Operations Research Perspectives. 2016, 1 (3), 43–58. https://doi.org/10.1016/j.orp.2016.09.002

Downloads

Published

2018-02-28

How to Cite

Urván Rivero, L. E., Ramírez Rodríguez, J., & López Bracho, R. (2018). Genetic algorithm for black and white coloring problem on graphs. Programación Matemática Y Software, 10(1), 17–23. https://doi.org/10.30973/progmat/2018.10.1/3

Issue

Vol. 10 No. 1 (2018): February, 2018

Section

Articles

License

Copyright (c) 2018 Programación Matemática y Software

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.