Defesa de Tese de Doutorado de Bruno José da Silva Barros – 27/03/2025, 09h30, por videoconferência
Link para defesa: https://meet.google.com/gko-jftc-exi
Variações do Problema da Árvore Geradora Mínima: Abordagens Algorítmicas e Estudo de Complexidade
Resumo:
Em muitas aplicações do mundo real, surge naturalmente a necessidade de resolver problemas relacionados a árvore geradora de um grafo. Apesar do problema clássico da árvore geradora mínima ser polinomial, muitas de suas generalizações são NP-difíceis. Três casos notáveis são as variantes conhecidas como Árvore Geradora Mínima Livre de Conflitos e Árvore Geradora Mínima Generalizada com e sem coleta de prêmios. A primeira variante surge, naturalmente, da necessidade de evitar conflitos entre elementos na solução de problemas. Dado um grafo não direcionado G=(V, E) onde cada aresta e E possui um peso positivo (e), e um grafo G=(V, E) tal que VE. No problema da Árvore Geradora Mínima Livre de Conflitos (AGMLC) é procurar (se existir) uma árvore geradora evitando arestas conflitantes com o menor custo, i.e., a solução mínima entre as árvores geradoras T tal que E(T) é um conjunto independente de G. Em contraste com o clássico problema polinomial da Árvore Geradora Mínima, determinar se uma instância I=(G, G) de AGMLC admite uma solução viável é um problema NP-completo. Neste trabalho, apresentamos uma análise diversificada da complexidade do AGMLC considerando várias classes de grafos para G e G. Em particular, foi possível concluir que o problema de determinar se uma instância I=(G, G) de AGMLC tem solução viável é NP-completo mesmo se G for um grafo planar bipartido subcúbico, e G for uma união disjunta de caminho de tamanho três (P3‘s). Além disso, se G é um grafo completo, e G é uma união disjunta de bicliques, então uma solução para I=(G, G) pode ser encontrada em tempo polinomial. Alguns resultados de (in)aproximabilidade para o AGMLC com G sendo um grafo completo também foram obtidos. Considerando a complexidade de resolver o AGMLC, é natural considerar uma abordagem por meta-heurísticas. Sendo assim, também foi feita uma abordagem baseada na meta-heurística GRASP unida à técnica de memória adaptativa. Isso resultou no GRASP-MA, que foi comparado com outros algoritmos da literatura, obtendo um desempenho muito satisfatório. Além disso, o conceito de GRASP com Memória Adaptativa também foi implementado para o problema da Árvore Geradora Mínima Generalizada com Coleta de Prêmios, que consiste em encontrar uma AGM contendo um vértice de cada uma das partições do conjunto de vértices. Por ter coleta de prêmio, o problema se torna diferente e mais desafiador do que a versão sem prêmios nos vértices. Para tratar problema da AGMGCP, foi demonstrado como eliminar arestas redundantes nas instâncias, diminuindo significativamente o número de arestas do grafo de entrada. Por fim, foi mostrado como acelerar a busca local da literatura, conseguindo reduzir em mais da metade o tempo de execução dos algoritmos.
Banca examinadora:
Prof. Luiz Satoru Ochi, UFF – Presidente
Prof. Uéverton dos Santos Souza, UFF
Prof. Igor Machado Coelho, UFF
Prof. Rian Gabriel Santos Pinheiro, UFAL
Prof. Luerbio Faria, UERJ
Prof. Bruno Costa e Silva Nogueira, UFAL