Data e hora: sexta, 5 de maio de 2023, às 16h
Local: sala 2077 (ICEx)
Palestrante: Marcio Santos (DCC, UFMG)
Resumo:
Um dos problemas mais estudados em teoria dos grafos é o problema de determinar o número cromático de um grafo. O número cromático é o menor número de cores necessário para colorir um grafo de forma que vértices adjacentes recebam cores distintas. Este problema é NP-Difícil e temos pouca esperança de resolver instâncias arbitrárias em tempo razoável.
Um caminho natural para lidar com esse problema em aplicações reais é o uso de heurísticas. Existem 2 heurísticas muito conhecidas para o problema: heurística gulosa e heurística B. Como heurísticas não possuem garantia de otimalidade, uma pergunta que surge é saber quão distante as soluções dadas por elas estão das soluções ótimas. Neste espírito nós estudamos dois parâmetros em grafos relacionados a estas heurísticas: o número de grundy e o número b-cromático.
