Comparación entre enfoques de programación de enteros para el problema de la tinción de Grundy

Vol 56, 2024 - 310088
Trabalho completo (Oral)
Favoritar este trabajo
¿Cómo citar este artículo?
Resúmenes
Dado un grafo G = (V, E), una coloración k es una forma de dividir el conjunto de vértices V en k conjuntos independientes, denotados por {V1, V2, . . . , Vk}. En un k- coloración, un vértice v ∈ Vi se considera un vértice de Grundy si es adyacente a algún vértice w ∈ Vj para todo j < i. El problema de coloración de Grundy busca Encuentre el valor más alto de k para el cual hay una coloración k, donde cada vértice en colorear ser un vértice Grundy. Este valor mayor de k se denomina número y está representada por Γ(G). En este trabajo, investigamos y comparamos tres formulaciones de programación entera: dos se basan en el modelo estándar de partición de vértices en clases de color, mientras que la tercera se basa en la formulación de representantes asimétricos.

¡Comparte tus ideas o preguntas con los autores!

¿Sabías que el mayor estímulo en el desarrollo científico y cultural es la curiosidad? ¡Deje sus preguntas o sugerencias al autor!

Inicia sesión para interactuar

¿Tiene alguna pregunta o sugerencia? ¡Comparte tus comentarios con los autores!

Instituciones
  • 1 UFC
  • 2 Universidade Federal do Ceará
Eje Temático
  • 14. OC – Otimização Combinatória
Palabras Clave
Teoría de grafos y algoritmos
Optimización combinatoria
Programación matemática
Tinción de vértices
Colorear Grundy