Universidad de Costa Rica
  • Sobre Kérwá
  • Acceso Abierto
  • Cómo Depositar
  • Políticas
  • Contacto
    • español
    • English
  • English 
    • español
    • English
  • Login
View Item 
  •   Kérwá Home
  • Publicaciones periódicas de la Universidad de Costa Rica
  • Revista de Matemática: Teoría y Aplicaciones
  • Revista de Matemáticas 12(1 y 2)
  • View Item
  •   Kérwá Home
  • Publicaciones periódicas de la Universidad de Costa Rica
  • Revista de Matemática: Teoría y Aplicaciones
  • Revista de Matemáticas 12(1 y 2)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta

Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta

artículo original
Thumbnail
View/Open
255-466-1-PB.pdf (195.7Kb)
Date
2012-03-22
Author
Lara Velázquez, Pedro
Gutiérrez Andrade, Miguel Ángel
Ramírez Rodríguez, Javier
López Bracho, Rafael
Metadata
Show full item record
Abstract
Let G and \bar{G} be two complementary graphs. Given a penalty function defined over the edges of \bar{G}, it is said that the rigidity of a k-coloring of G is the summation ofthe penalties of the edges of G that join vertices whose endpoint are equally colored. Based on this previous definition, the Robust Coloring Problem is set when searching the valid k-coloring of minimum rigidity. Yáñez and Ramírez proved that this is an NP-hard problem. In this work we present an evolutive algorithm based in the scatter search technique, which obtains optimal solutions for those instances for which an optimal solution is known, and obtains the best known solutions compared to other heuristics, such as: simulated annealing, tabu search and partial enumeration.
 
Sean G y bar{G} un par de gráficas complementarias. Dada una función de peso definida sobre las aristas de \bar{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 \bar{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 óptima, y obtiene las mejores soluciones conocidas comparadas con otras heurísticas, tales como: recocido simulado, búsqueda tabú y enumeración parcial.
 
URI
https://hdl.handle.net/10669/12901
External link to the item
10.15517/rmta.v12i1-2.255
http://revistas.ucr.ac.cr/index.php/matematica/article/view/255
Collections
  • Revista de Matemáticas 12(1 y 2) [17]



  • Repositorios universitarios

  • Repositorio del SIBDI-UCR
  • Biblioteca Digital del CIICLA
  • Repositorio Documental Rafael Obregón Loría (CIHAC)
  • Biblioteca Digital Carlos Melendez (CIHAC)
  • Repositorio de Fotografías
  • Colección de videos de UPA-VAS
  • Sitios recomendados

  • Buscador regional de LA Referencia
  • Buscador del Open ROAR
  • Scientific Electronic Library Online (SciELO)
  • Directory of Open Access Journals (DOAJ)
  • Redalyc
  • Redes sociales

  • facebook.com/repositoriokerwa
  • @Ciencia_UCR
  • Sobre Kérwá
  • Acceso Abierto
  • Cómo depositar
  • Políticas
Contact Us | Send Feedback
Repositorio Institucional de la Universidad de Costa Rica. Algunos derechos reservados. Este repositorio funciona con DSpace.
 

 

Browse

All of KérwáCommunities & CollectionsTitlesAuthorsSubjectsProcedenceTypeThis CollectionTitlesAuthorsSubjectsProcedenceType

My Account

LoginRegister

Statistics

View Usage Statistics

  • Repositorios universitarios

  • Repositorio del SIBDI-UCR
  • Biblioteca Digital del CIICLA
  • Repositorio Documental Rafael Obregón Loría (CIHAC)
  • Biblioteca Digital Carlos Melendez (CIHAC)
  • Repositorio de Fotografías
  • Colección de videos de UPA-VAS
  • Sitios recomendados

  • Buscador regional de LA Referencia
  • Buscador del Open ROAR
  • Scientific Electronic Library Online (SciELO)
  • Directory of Open Access Journals (DOAJ)
  • Redalyc
  • Redes sociales

  • facebook.com/repositoriokerwa
  • @Ciencia_UCR
  • Sobre Kérwá
  • Acceso Abierto
  • Cómo depositar
  • Políticas
Contact Us | Send Feedback
Repositorio Institucional de la Universidad de Costa Rica. Algunos derechos reservados. Este repositorio funciona con DSpace.