Formulations and Sequential and Parallel Algorithms for the Minimum Cost Spanning Tree Problem with Minimum Degree Constraint

• Leonardo Conegundes Martinez UFMG
• Alexandre Salles da Cunha UFMG

Abstract

Given an edge weighted undirected graph G and a positive integer d, the Min-degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree T of G, such that each vertex is either a leaf or else has a degree at least d in T . In this work, we introduce Integer Programming formulations and present sequential and parallel optimization algorithms for the problem. With the proposed methods, several new optimality certificates and best lower and upper bounds for MDMST are provided.

References

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.