Resultados de NP-dificuldade e Aproximação para o Problema da k−Floresta Geradora Minimamente Rotulada - Corrêa, Kennedy; Campêlo, Manoel (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.8860, 2025)
Dado um grafo colorido em arestas G, o problema da k-floresta geradora minimamente rotulada consiste em encontrar uma floresta geradora F de G com número mínimo de cores e número de componentes limitado por k. Neste trabalho, apresentamos uma prova da NP-completude do problema em grafos split e propomos um algoritmo aproximativo para solucioná-lo.