Propriedades do Problema da Floresta Geradora k-Rotulada - de Abreu Figueredo, Pedro Jorge; Campêlo, Manoel (Anais do Encontro de Teoria da Computação (ETC), 2020)
Consideramos o problema da Floresta Geradora k-Rotulada, que consiste em encontrar uma floresta geradora de um grafo colorido em arestas com a menor quantidade de árvores e no máximo k cores. Derivamos duas caracterizações para o problema e mostramos estratégias para converter uma instância em outra equivalente. Esses resultados impactam o desenvolvimento de abordagens de solução. Identificamos também alguns casos polinomiais.