INVESTIGADORES
ZABALA Paula Lorena
congresos y reuniones científicas
Título:
Coloreo de aristas propio con distinción de vértices adyacentes
Autor/es:
BRIAN CURCIO; ISABEL MÉNDEZ-DÍAZ; PAULA ZABALA
Lugar:
Ciudad de Buenos Aires
Reunión:
Simposio; Simposio Argentino de Investigación Operativa, 45 JAIIO: Jornadas Argentinas de Informática; 2016
Institución organizadora:
Sociedad Argentina de Informática e Investigación Operativa
Resumen:
El Coloreo de aristas propio con distinción de vértices 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 vértices adyacentes sea distinguible por los colores de sus aristas incidentes.Este problema fue ampliamente estudiado desde un punto de vista teórico 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 utilizando programación lineal entera, proponemos un modelo para resolver nuestro problema.Estudiamos el poliedro de la formulación, conjeturamos un sistema minimal de ecuaciones y caracterizamos algunas familias de desigualdades válidas. Finalmente desarrollamos un algoritmo Branch and Cut que utiliza las desigualdades encontradas obteniendo buenos resultados en instancias de grafos aleatorios.
