Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | es |
| Published: |
Universidad de Costa Rica
2005
|
| Subjects: | |
| Online Access: | https://www.redalyc.org/articulo.oa?id=45326946010 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta. Pedro Lara Velázquez Miguel Angel Gutiérrez Andrade Javier Ramírez Rodríguez Rafael López Bracho Física, Astronomía y Matemáticas heurísticas Búsqueda dispersa optimización discreta coloración de gráficas optimización combinatoria Sean G y G un par de gráficas complementarias. Dada una función de peso definida sobre las aristas de G , se dice que la rigidez de una k -coloración válida de G es la suma de los pesos de las aristas de G que unen vértices del mismo color. Con base en la anterior definición, se plantea el Problema de Coloración Robusta al buscar la k -coloración válida de rigidez mínima. Yáñez y Ramírez probaron que este problema es NP -duro. En este trabajo se presenta un algoritmo evolutivo basado en la técnica de búsqueda dispersa, la cual obtiene soluciones óptimas, en las instancias para las que se conoce la solución optima, y obtiene las mejores soluciones conocidas comparadas con otras heurísticas, tales como: recocido simulado, búsqueda tabú y enumeración parcial. 2005 artículo científico 1409-2433 https://www.redalyc.org/articulo.oa?id=45326946010 es http://www.redalyc.org/revista.oa?id=453 Revista de Matemática: Teoría y Aplicaciones application/pdf Universidad de Costa Rica Revista de Matemática: Teoría y Aplicaciones (Costa Rica) Num.1-2 Vol.12