| Revista: | Programación matemática y software |
| Base de datos: | |
| Número de sistema: | 000573162 |
| ISSN: | 2007-3283 |
| Autores: | , , , |
| Año: | 2018 |
| Volumen: | 10 |
| Número: | 1 |
| Paginación: | 17-23 |
| País: | México |
| Idioma: | Español |
| Resumen en inglés | 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]. |
| Resumen en español | 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 |
| Keyword: | Anticoloring, Genetic Algorithm, BWC |
| Texto completo: | Texto completo (Ver PDF) |
