Impacto de Técnicas de Pré-Processamento em Algoritmo de Branch-and-Price para o Problema de Coloração de Grafos - Romero, Ieremies V. F.; Schouery, Rafael C. S. (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.9224, 2025)
Este trabalho investiga o problema de coloração de vértices, o qual possui aplicações em escalonamento e alocação de recursos. Descrevemos um pré-processamento que utiliza técnicas de separação e redução (k-core ) para diminuir o espaço de busca sem comprometer limites inferiores válidos. Resultados experimentais com instâncias do DIMACS demonstram que o pré-processamento aumenta a quantidade de instâncias resolvidas, apesar de, em alguns casos, a ordem com que as partes do grafo são resolvidas por comprometer a capacidade de resolvê-lo. Concluimos com sugestões para trabalhos futuros, como a incorporação de separadores por clique.