Coloreo de aristas propio con distinción de vértices adyacentes

El Coloreo de aristas propio con distinci´on de v´ertices adyacentes es el problema de encontrar la menor cantidad de colores necesarios para colorear las aristas de un grafo tal que sea un coloreo propio de aristas y cumpla la propiedad que cada par de vertices adyacentes sea distinguible por los c...

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: 2016
Materias:
Ciencias Informáticas
branch and cut
estudio poliedral
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/58541
http://45jaiio.sadio.org.ar/sites/default/files/Sio-15.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-58541
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
branch and cut
estudio poliedral
spellingShingle Ciencias Informáticas
branch and cut
estudio poliedral
Curcio, Brian
Méndez Díaz, Isabel
Zabala, Paula
Coloreo de aristas propio con distinción de vértices adyacentes
topic_facet Ciencias Informáticas
branch and cut
estudio poliedral
description El Coloreo de aristas propio con distinci´on de v´ertices adyacentes es el problema de encontrar la menor cantidad de colores necesarios para colorear las aristas de un grafo tal que sea un coloreo propio de aristas y cumpla la propiedad que cada par de vertices adyacentes sea distinguible por los colores de sus aristas incidentes. Este problema fue ampliamente estudiado desde un punto de vista te´orico [ZLW02,BGrLS07,WW10] pero no se encuentran en la literatura algoritmos para resolver el problema. Debido a los buenos resultados obtenidos en distintos problemas de etiquetado de grafos [NP91,MDZ06] utilizando programaci´on lineal entera, proponemos un modelo para resolver nuestro problema. Estudiamos el poliedro de la formulaci´on, conjeturamos un sistema minimal de ecuaciones y caracterizamos algunas familias de desigualdades v´alidas. Finalmente desarrollamos un algoritmo Branch and Cut que utiliza las desigualdades encontradas obteneniendo buenos resultados en instancias de grafos aleatorios.
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 Coloreo de aristas propio con distinción de vértices adyacentes
title_short Coloreo de aristas propio con distinción de vértices adyacentes
title_full Coloreo de aristas propio con distinción de vértices adyacentes
title_fullStr Coloreo de aristas propio con distinción de vértices adyacentes
title_full_unstemmed Coloreo de aristas propio con distinción de vértices adyacentes
title_sort coloreo de aristas propio con distinción de vértices adyacentes
publishDate 2016
url http://sedici.unlp.edu.ar/handle/10915/58541
http://45jaiio.sadio.org.ar/sites/default/files/Sio-15.pdf
work_keys_str_mv AT curciobrian coloreodearistaspropiocondistinciondeverticesadyacentes
AT mendezdiazisabel coloreodearistaspropiocondistinciondeverticesadyacentes
AT zabalapaula coloreodearistaspropiocondistinciondeverticesadyacentes
bdutipo_str Repositorios
_version_ 1764820477999579137

Ejemplares similares