# Min-Degree Constrained Minimum Spanning Tree Problem: Complexity, proprieties and formulations

### Authors

### Abstract

Given an undirected graph G = (V , E) and a function d : V ' N , the Min-DegreeConstrained Minimum Spanning Tree (md-MST) problem is to find a minimum cost

spanning tree T of G where each node i ' V has minimum degree d(i) or is a leaf

node. This problem is closely related with the well-known Degree Constrained Minimum

Spanning Tree (d-MST) problem, where the degree constraint is an upper limit instead.

In this paper we prove that the md-MST problem is NP-hard and present some pro-

prieties, namely upper and lower limits to the number of central nodes and leaf-nodes

in any feasible solution to the problem. Flow based formulations are also proposed and

computational experiments involving the associated LP relaxations are presented. These

results indicate that, for similar formulations to both d-MST and md-MST problems, the

LP versions of the d-MST stronger flow models seem to provide a better approximation

to the integer polyhedron than the correspondent md-MST flow formulations (within the

linear relaxation context), which seems to indicate that it might be harder to get good

formulations to the later problem.

### Keywords

Degree constrained spanning tree problems, complexity, single-commodity flow formula- tions, multicommodity flow formulations### Subject

Operations Research### TechReport Number

6### PDF File

### Cited by

#### Year 2013 : 1 citations

M. Campelo, R.C.de Andrade, F.C.S. Dias, C.P. de Sousa,"Problema da árvore geradora mínima com restrição de grau mínimo e centrais fixos", Proc. Simpósio Brasileiro de Pesquisa Operacional, Natal, Brasil, 2013.

#### Year 2012 : 2 citations

Javad Akbari Torkestani, Mobility-Based Backbone Formation in Wireless Mobile Ad-hoc Networks,

Wireless Personal Communications, Springer New York,

http://dx.doi.org/10.1007/s11277-012-0955-1

L. C. Martinez e A. S. da Cunha, ”A parallel lagragian relaxation algorithm for the min-degree constrained spanning tree pro- blem”. In Porc. 2cd. Intl. Conf. Combinatorial Optimiza- tion, 237-248, Springer Berlin, 2012. (DOI: 10.1007/978-3-642-32147-4 22)

#### Year 2011 : 1 citations

Leonardo Conegundes Martinez and Alexandre Salles da Cunha: "The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm". Discrete Applied Mathematics, Available online 13 September 2011 (in print).

#### Year 2010 : 2 citations

”Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm”, L.

C. Martinez e A. S. da Cunha, Electronic Notes in Discrete Mathematics, 36(1): 311-318,

2010.

“Min-degree constrained minimum spanning tree problem: New formulation via Miller-

Tucker-Zemlin constraints”, I. Akgun and B. Tansel, Computers & Operations Research,

37(1): 72-82, 2010.

#### Year 2009 : 2 citations

"VNS and second order heuristics for the min-degree constrained minimum spanning tree problem", Pedro Martins and Mauricio C. de Souza, Computers and Operations Research, November 2009

”Problema da ´arvore de suporte de custo m´?nimo com restric¸ ˜ao de grau e custos associados aos nodos”, P.M. Moura , Tese de doutoramento, Universidade de Lisboa, Faculdade de Ciências, 2009.