Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles

El problema de suma de coloreo de aristas con vértices adyacentes distinguibles (AVDSECP) consiste en buscar una asignación de colores a las aristas de un grato con las siguientes restricciones: todo par de aristas adyacentes tienen distinto color y todo par de vértices adyacentes debe tener diferen...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Curcio, Brian, Méndez-Díaz, Isabel, Zabala, Paula
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2021
Materias:
Ciencias Informáticas
Heurísticas
Coloreo de aristas
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/141766
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-16.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-141766
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
Heurísticas
Coloreo de aristas
spellingShingle Ciencias Informáticas
Heurísticas
Coloreo de aristas
Curcio, Brian
Méndez-Díaz, Isabel
Zabala, Paula
Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles
topic_facet Ciencias Informáticas
Heurísticas
Coloreo de aristas
description El problema de suma de coloreo de aristas con vértices adyacentes distinguibles (AVDSECP) consiste en buscar una asignación de colores a las aristas de un grato con las siguientes restricciones: todo par de aristas adyacentes tienen distinto color y todo par de vértices adyacentes debe tener diferencia en el conjunto de colores asignados a sus aristas incidentes. El objetivo es minimizar la suma de los colores a asignar tal que se cumplan las restricciones. Este problema es un caso particular de una gran familia de problemas conocida bajo el nombre de etiquetado de gratos, que resultan una herramienta muy útil para modelar situaciones de la vida cotidiana. Dada la pertenencia del AVDSECP a la clase de problemas NP-Difícil, en este trabajo presentaremos diferentes enfoques heurísticos para resolverlo. Agrupamos a estas heurísticas en dos categorías: procedimientos rápidos y procedimientos lentos (ya que consumen una cantidad de tiempo considerable teniéndose en cuenta que no son procedimientos exactos). Según el contexto de aplicación serán útiles unas u otras. Dentro de los procedimientos rápidos incluimos una heurística golosa. Además estudiamos dos modelos de programación por restricciones, uno de ellos enmarcado dentro de los métodos rápidos y el otro dentro de los lentos. También dentro del grupo de los procedimientos lentos, expondremos una heurística basada en una formulación de programación lineal entera con cantidad de variables exponencial, a la cual le aplicamos un proceso de generación de columnas. Presentaremos experimentos computacionales para analizar la performance de las diferentes heurísticas, buscando identificar cuales son los criterios que brindan el mejor rendimiento en cada una. Finalmente, concluiremos con una comparación entre las diferentes propuestas.
format Objeto de conferencia
Resumen
author Curcio, Brian
Méndez-Díaz, Isabel
Zabala, Paula
author_facet Curcio, Brian
Méndez-Díaz, Isabel
Zabala, Paula
author_sort Curcio, Brian
title Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles
title_short Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles
title_full Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles
title_fullStr Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles
title_full_unstemmed Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles
title_sort heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles
publishDate 2021
url http://sedici.unlp.edu.ar/handle/10915/141766
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-16.pdf
work_keys_str_mv AT curciobrian heuristicasparaelproblemadesumadecoloreodearistasconverticesadyacentesdistinguibles
AT mendezdiazisabel heuristicasparaelproblemadesumadecoloreodearistasconverticesadyacentesdistinguibles
AT zabalapaula heuristicasparaelproblemadesumadecoloreodearistasconverticesadyacentesdistinguibles
bdutipo_str Repositorios
_version_ 1764820459731288066

Ejemplares similares