Título: Heurísticas para coloração k-imprópria

Horário: 10:00h

Data: 06/03/2020

Local: Bloco 952 - Sala de Seminários

Resumo:

Uma coloração dos vértices de um grafo $G = (V,E)$ é própria se vértices adjacentes recebem cores diferentes. Estudamos neste trabalho uma relaxação desse problema, chamada de coloração $k$-imprópria, onde, dado um inteiro positivo $k$, a cor de um vértice qualquer pode ser compartilhada com até $k$ de seus vizinhos. Uma vez que a coloração própria é uma coloração $0$-imprópria, a coloração $k$-imprópria é igualmente um problema difícil, podendo-se, analogamente, abordar o problema através do uso de heurísticas. Neste trabalho, estudamos três heurísticas para o problema de coloração $k$-imprópria de grafos. Como se faz habitualmente, o estudo aqui almejava estimar o pior desempenho dessas heurísticas. As heurísticas escolhidas foram as heurísticas gulosa, $a$ e $b$, que só haviam sido definidas até então para colorações próprias. No caso das heurísticas $a$ e $b$, as suas
versões $k$-impróprias foram definidas e, no caso da heurística $b$, provamos que a sua aplicação pode não convergir. No caso da heurística gulosa, além de introduzir o conceito de Número de Grundy $k$-impróprio, generalizamos o conceito de $t$-átomo, estudamos o parâmetro em árvores binomiais e cografos e apresentamos formulações de programação por restrições e programação inteira, não apenas para a coloração gulosa imprópria, mas também para o Número de Grundy clássico, preenchendo um vácuo naquele estudo.

Banca:

• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC - Orientadora)
• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC)
• Prof. Dr. Tibérius de Oliveira e Bonates (UFC)
• Prof. Dr. Vinicius Fernandes dos Santos (UFMG)