Otimização Combinatória: Problemas de Árvores em Grafos
Autores
4089 |
539,44
|
|
4090 |
539,44
|
Informações:
Publicações do PESC
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.
In this Thesis, we presented models and algorithms for problems related with the Spanning Tree problem. Three problems were studied: the Hop constrained Minimal Spanning Tree Problem (HMSTP), the Diameter constrained Minimal Spanning Tree Problem (DMSTP) and the Maximum Leaf Spanning Tree Problem (MLSTP). We propose two new formulations for the HMSTP and the DMSTP problems based on layered directed graph. In fact, this is equivalent to transform the problems into a suitable directed Steiner Tree Problem (STP) over that layered graph. Experiments show a significant increase with respect to previous methods. We propose a reformulation for the MLSTP, stronger than the original one, and another transformation to STP. Extensive computational experiments were carried out in order to evaluate the methods. A significant gain in performance with respect to previous methods shows the strength of the approachs.