Modelo de Programação Linear Inteira Mista para o Problema de Super-Coloração

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.