Let G=(V,E) be a connected weighted undirected graph. Given a positive integer d, the Min-Degree Constrained Minimum Spanning Tree (md-MST)} problem consists in finding a spanning tree T for G having minimum total edge cost and such as each node i in the tree either has degree at least d or is a leaf node. In the present work we prove that this recently introduced combinatorial problem is NP-hard in general.
Keywords
NP-hardness, complexity proof, combinatorial problem
Subject
Complexity Theory
Conference
ISCO 2010 International Symposium in Combinatorial Optimization, , Electronic Notes in Discrete Mathematics, 36:9-15, 2010, March 2010
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.
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 : 2 citations
Chun-Chao Yeh and Ying-Che Chien, "A PARTICLE SWARM OPTIMIZATION-LIKE ALGORITHM FOR CONSTRAINED MINIMAL SPANNING TREE PROBLEM", Journal of Marine Science and Technology, Vol. 22, No. 3, pp. 341-351 (2014 ) 341 DOI: 10.6119/JMST-013-1119-2
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.
Year 2013 : 2 citations
Torkestani, J.A., ”A Learning Automata-based algorithm to the Stochastic Min-Degree Constrained Minimum Spanning Tree Problem”. International Journal of Foundations of Computer Science, 24(03):329-348, 2013.(DOI: 10.1142/S012905411350007X)
V. Venkata Ramana Murthy, Alok Singh, "An Ant Colony Optimization Algorithm for the Min-Degree Constrained Minimum Spanning Tree Problem", Swarm, Evolutionary, and Memetic Computing, Lecture Notes in Computer Science, Volume 8298, 2013, pp 85-94.
Year 2012 : 2 citations
Torkestani, J.L.,”Mobility-based Backbone Formation in Wireless Mobile Ad-hoc Networks”. Wireless Personal Communications, Springer US, 2012, 7422:237-248, 2012.(DOI: 10.1007/s1277-012-0955-1)
L. C. Martinez e A. S. da Cunha, ”A Parallel Lagrangian Relaxation Algorithm for the Min-Degree Constrained Minimum Spanning Tree Problem”. Combinatorial Optimization, 7422:237-248, 2012.
Year 2011 : 1 citations
Leonardo Conegundes Martinez, 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, ISSN 0166-218X, http://dx.doi.org/10.1016/j.dam.2011.08.008.
