INVESTIGADORES
ZABALA Paula Lorena
congresos y reuniones científicas
Título:
Heurísticas para resolver el problema de k,i-coloreo de grafos
Autor/es:
ISABEL MÉNDEZ-DÍAZ; PAULA ZABALA
Lugar:
Buenos Aires
Reunión:
Congreso; IX CLAIO Congreso Latinoiberoamericano de Investigación Operativa; 1998
Institución organizadora:
Asociación Latino-Iberoamericana de Investigación Operativa
Resumen:
El objetivo de este trabajo es presentar un algoritmo para resolver el problema de k,i-coloreo de grafos. Este problema es una generalización del problema de coloreo de grafos. No existe hasta el momento tratamiento de este problema en la bibliografía. Se han demostrado para algunas instancias que el problema es NP-Hard y se conjetura que esta afirmación es válida para el caso general. Debido a esta última afirmación, se ha desarrollado una heurística. Para evaluar la performance de esta heurística, se utilizó un modelo de programación lineal 0-1, el cual fue resuelto mediante diferentes variantes de un algoritmo Branch and Cut.
