Modelo de Programação Linear Inteira Mista para o Problema de Super-Coloração
Author:
Pacheco, Rafael Marian
Abstract:
Em um grafo G = (V, E), no qual cada vértice v ∈ V possui uma cor (que pode ser igual
a de seus vizinhos), o problema da Super-coloração de v visa encontrar a quantidade máxima
de cores que existe em um caminho simples a partir de v. O problema é NP-Difícil, o que torna
a busca por novos métodos exatos e heurísticos foco de investigação em pesquisa na área de
Ciência da Computação. A Super-coloração tem aplicações na área da Antropologia, na qual
as cores representam famílias ou clãs. Neste contexto, a presente proposta tem o objetivo de
propor e analisar métodos exatos para resolver o problema. Para isto, pretende-se realizar um
levantamento da literatura na área, propor desenvolver algoritmos e apresentar os resultados à
comunidade científica.
