Data: 30/04/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Algoritmos Exatos e Heurísticas de Colorações de Grafos
Palestrante: Cláudia Linhares Sales (UFC)


Resumo: Dado um grafo G = (V, E), colorir os vértices de G significa atribuir cores aos mesmos de forma que vértices adjacentes tenham cores distintas. O número cromático de um grafo é o menor inteiro k tal que G admite uma coloração de vértices com k cores. Nessa palestra, veremos algoritmos combinatórios exatos de coloração na classe de grafos perfeitos, usando o conceito de pares de amigos, além de heurísticas clássicas de coloração, com a definição de seus parâmetros relacionados, apresentando as ferramentas usadas para lidar com a determinação desses parâmetros.