| Autor: |
Luis Eduardo Urván Rivero, Javier Ramírez Rodríguez, Rafael López Bracho |
| Rok vydání: |
2018 |
| Zdroj: |
Programación Matemática y Software. 10 |
| ISSN: |
2007-3283 |
| DOI: |
10.30973/progmat/2018.10.1/3 |
| Popis: |
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]. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
