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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Español |
| Publicado: |
2016
|
| Materias: | |
| 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: |
| Sumario: | 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. |
|---|