This paper addresses a new combinatorial problem, the Min-Degree Constrained Minimum Spanning Tree (md-MST), that can be stated as: given a weighted undirected graph G = (V,E) with positive costs on the edges and a node-degrees function d : V ? N, the md-MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of d(i) or is a leaf node. This problem is closely related to the well-known Degree Constrained Minimum Spanning Tree (d-MST) problem, where the degree constraint is an upper bound instead. The general NP-hardness for the md-MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow based formulations are proposed and computational experiments involving the associated LP relaxations are presented.
Keywords
degree constrained spanning tree problems;computational complexity;single-commodity flow formulations;multicommodity flow formulations
Subject
Operations Research and Complexity Theory
Journal
ITOR International transactions in Operational Research, Vol. 19, #3, pp. 323-352, Wiley, May 2012
Cited by
Year 2016 : 2 citations
Mashreghi, A., Zarei, A., "When Diameter Matters: Parameterized Approximation Algorithms for Bounded Diameter Minimum Steiner Tree Problem", Theory of Computing Systems 58 (2), pp. 287-303.
da Cunha, A.S., Simonetti, L., Lucena, A. "A strong symmetric formulation for the Min-degree Constrained Minimum Spanning Tree Problem", Electronic Notes in Discrete Mathematics 52, pp. 237-244.
Year 2015 : 1 citations
Ali Mashreghi , Alireza Zarei . "When Diameter Matters: Parameterized Approximation Algorithms for Bounded Diameter Minimum Steiner Tree Problem". Theory of Computing Systems (Fev. 2016), Vol. 58, Issue 2, pp 287-303. (available online: 24 March 2015)
Year 2014 : 3 citations
L. Gouveia, P. Moura, M. Ruthmair, A. Sousa. "Spanning Trees with variable degree bounds", Tech. Report TR–186–1–14–02, UT WIEN
Institut für Computergraphik und Algorithmen, January, 2014.
Leonardo Conegundes Martinez , Alexandre Salles da Cunha, "The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm", Discrete Applied Mathematics, 164(1):210–224, 2014.
L. Gouveia, P. Moura, M. Ruthmair, A. Sousa, Spanning trees with variable degree bounds, European Journal of Operational Research, Available online 1 June 2014, ISSN 0377-2217, http://dx.doi.org/10.1016/j.ejor.2014.05.034
Year 2013 : 5 citations
JAVAD AKBARI TORKESTANI, "A LEARNING AUTOMATA-BASED ALGORITHM TO THE STOCHASTIC MIN-DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM", International Journal of Foundations of Computer Science, April 2013, Vol. 24, No. 03 : pp. 329-348 (doi: 10.1142/S012905411350007X)
Ruiz y Ruiz, H., The capacitated minimum spanning tree problem, PhD thesis, Dep. Matemática, Universitat Politècnica de Catalunha, 2013.
Akbari Torkestani, Javad, "Mobility-Based Backbone Formation in Wireless Mobile Ad-hoc Networks", Wireless Personal Communications, 71(4):563-2586, Springer US, doi=10.1007/s11277-012-0955-1
Gouveia, L., Moura P., de Sousa, A., Spanning Trees with variable degree bounds, CIO ? Working Paper 1/2013, Universidade de Lisboa, 2013.
Francesco Carrabs, Raffaele Cerulli, Manlio Gaudioso, Monica Gentili,
Lower and upper bounds for the spanning tree with minimum branch vertices,
Computational Optimization and Applications, 1-34, April 2013, Springer US
http://dx.doi.org/10.1007/s10589-013-9556-5
Year 2012 : 1 citations
Martinez, L. and da Cunha, A., ”A Parallel Lagrangian Relaxation Algorithm for the Min- Degree Constrained Minimum Spanning Tree Problem”, Combinatorial Optimization, 7422:237- 248, Springer US, 2012.
Year 2011 : 1 citations
Martinez, L. and da Cunha, A."The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm", Discrete Applied Mathematics, Volume 164, Part 1, 2014, Pages 210–224
Year 2010 : 1 citations
Martinez, L., da Cunha, A.,"Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm", Electronic Notes in Discrete Mathematics, Volume 36, 1 August 2010, Pages 311–318
