Estudo de Coloração de Grafos Aplicado ao Problema de Alocação de Horários: Uma Solução Focada no Aluno - Barbosa, François; Jeovane, José; Avelino, Guilherme; Magalhães, Arlino (Anais da Escola Regional de Computação do Ceará, Maranhão e Piauí (ERCEMAPI), 2024)
A pesquisa explora a aplicação da Teoria dos Grafos no problema de alocação de horários, focando nos alunos em ano de conclusão de curso. Utilizando a coloração de grafos, as disciplinas foram representadas como vértices e os alunos como arestas. Foram comparadas duas abordagens principais: o algoritmo de Força Bruta e a heurística Degree of Saturation (DSATUR). Os resultados mostraram que, embora o algoritmo de Força Bruta forneça uma solução ótima, ele é computacionalmente caro. Em contrapartida, a heurística DSATUR demonstrou ser extremamente eficiente em termos de tempo de execução, embora não garanta sempre a solução ótima. O código da aplicação proposta está disponível no Google Colab .