Formulações e Algoritmos Sequenciais e Paralelos para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau Mínimo

• Leonardo Conegundes Martinez UFMG
• Alexandre Salles da Cunha UFMG

Resumo

Dados um grafo não direcionado valorado nas arestas G e um inteiro positivo d, o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau Mínimo (PAGMGM) consiste em encontrar uma árvore geradora de custo mínimo T de G, tal que o grau de cada vértice em T seja igual a 1 ou maior ou igual a d. Neste trabalho, introduzimos formulações de Programação Inteira e algoritmos de otimização sequenciais e paralelos para o problema. Com os métodos propostos, vários novos certificados de otimalidade e melhores limites inferiores e superiores para o PAGMGM são fornecidos.

Referências

Akgún, I. and Tansel, B. (2010). Min-degree constrained minimum spanning tree problem: New formulation via Miller-Tucker-Zemlin constraints. Computers & Operations Research, 37(1):72–82.

Almeida, A. M., Martins, P., and Souza, M. C. (2006). Min-Degree Constrained Minimum Spanning Tree Problem: Complexity, proprieties and formulations. Technical Report 6/2006, Centro de Investigação Operacional, Universidade de Lisboa.

Almeida, A. M., Martins, P., and Souza, M. C. (2010). md-MST is NP-hard for d ≥ 3. Electronic Notes in Discrete Mathematics, 36:9–15.

Gouveia, L. and Telhada, J. (2008). The multi-weighted Steiner Tree problem: A reformulation by intersection. Computers & Operations Research, 35:3599–3611.

Martinez, L. C. (2012). Formulações e algoritmos sequencias e paralelos para o problema da Árvore geradora de custo mínimo com restrição de grau mínimo. Master’s thesis, Departamento de Ciência da Computação, Universidade Federal de Minas Gerais.

Martinez, L. C. and Cunha, A. S. (2010). Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm. Electronic Notes in Discrete Mathematics, 36:311–318. ISCO International Symposium on Combinatorial Optimization.

Martinez, L. C. and Cunha, A. S. (2011). The Min-Degree Constrained Minimum Spanning Tree Problem: Formulations and Branch-and-cut algorithm. Discrete Applied Mathematics. In Press, DOI: 10.1016/j.dam.2011.08.008.

Martinez, L. C. and Cunha, A. S. (2012). A parallel lagrangian relaxation algorithm for the min-degree constrained minimum spanning tree problem. Lecture Notes in Computer Science, 7422:237–248.

Martins, P. and Souza, M. C. (2009). VNS and second order heuristics for the min-degree constrained minimum sp anning tree problem. Computers & Operations Research, 36:2669–2982.