Variações do Problema da Árvore Geradora Mínima: Abordagens Algorítmicas e Estudo de Complexidade

Em um mundo hiperconectado, projetar redes eficientes, sejam de computadores, transporte ou energia, é um desafio fundamental. No coração desses projetos está o clássico problema da Árvore Geradora Mínima (AGM). Mas e quando a realidade impõe restrições? E quando certas conexões não podem coexistir ou a seleção de um nó envolve incentivos? É nesse cenário que esta tese de doutorado se destaca, oferecendo contribuições de alto impacto para a área de Otimização Combinatória. A pesquisa mergulha em duas variações complexas e NP-difíceis da AGM: a Árvore Geradora Mínima Livre de Conflitos (AGMLC) e a Árvore Geradora Mínima Generalizada com Coleta de Prêmios (AGMGCP). Indo muito além da solução tradicional, este trabalho entrega um pacote completo que combina teoria de ponta com algoritmos eficientes.