Genetic algorithm for black and white coloring problem on graphs

Publicación:
Entidad Editora:
Editor Técnico:
ISSN:
Ejemplar/Número:

Cateoría:
Páginas:
Colección:
Fecha de inicio:
Periodicidad:

Programación Matemática y Software
Universidad Autónoma del Estado de Morelos
Dr.Marco Antonio Cruz Chávez
2007-3283

Volumen 10, Número 1 /Febrero de 2018
Periodo Febrero-Mayo 2018
Artículo de Investigación
17-23
Computación

Febrero del 2018

Cuatrimestral

 

 

 

 

PDF(231 KB)

Luis Eduardo Urbán Rivero1, Javier Ramírez Rodríguez2, Rafael López Bracho2

1 Posgrado en optimización UAM Azcapotzalco.

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

Recibido: 11 de julio del 2017 Aceptado: 20 de octubre del 2017 Publicado en línea: 28 de febrero del 2018

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].


Keywords: Anticoloring, Genetic algorithm, BWC.

 

Resumen.Un problema clásico en la teoría de gráficas es el conocido como problema de coloración (GC por sus siglas en inglés). Este problema consiste en asignar colores a los vértices de la gráfica tal que vértices adyacentes deben tener colores diferentes. El objetivo de este problema es encontrar el mínimo número de colores necesarios para colorear la gráfica bajo la mencionada condición de coloración. En el caso del problema de anticoloración (GAC por sus siglas en inglés), la forma de asignar color es opuesta. En este caso vértices adyacentes deben tener el mismo color o al menos uno de ellos no debe tener color. En este problema el objetivo es diferente en el sentido del número de colores que en este caso es fijo. Este problema puede ser convertido en un problema de optimización. El GAC es NP-Completo aun cuando se usen sólo dos colores [2]. En este trabajo trataremos con el caso especial de dos colores del GAC mediante el uso de algoritmos genéticos y se compara con la búsqueda Tabú que es la mejor técnica conocida para la solución de este problema [3].


Palabras Clave:Anticoloración, Algoritmo genético, BWC.

Luis Eduardo Urbán Rivero (Autor de correspondencia)
Email:lurbanrivero@gmail.com
 
Javier Ramírez Rodríguez
Email: jararo@azc.uam.mx
 
Rafael López Bracho
Email: rlb@azc.uam.mx