Otimização Combinatória: Problemas de Árvores em Grafos

Neste trabalho, apresentamos modelos e algoritmos para problemas relacionados ao problema de árvore geradora. Três problemas foram estudados: o Problema de Arvore Geradora Mínima com restrição de Nível (PAGMN), o Problema de Árvore Geradora Mínima com restrição de Diâmetro (PAGMD) e o Problema de Árvore Geradora com número Máximo de Folhas (PAGMF). Apresentamos modelos para o PAGMN e o PAGMD, onde o problema é reformulado em grafos direcionados em níveis. Na verdade, isto é equivalente á transformação desses problemas em um Problema de Árvore de Steiner Direcionada (PASD) no grafo em níveis. Os testes computacionais realizados mostraram um grande ganho em relação aos métodos anteriores para os dois problemas. Para o PAGMF, apresentamos uma reformulação direcionada de uma formulação proposta na literatura, que se mostrou mais forte que a original. Introduzimos também uma reformulação do problema em termos do PASD. Para este problema, os teste computacionais também mostraram um ganho em relação aos métodos propostos na literatura.