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 formulationsSubject
Operations ResearchTechReport Number
6PDF 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.