https://hal-lirmm.ccsd.cnrs.fr/lirmm-00745713Merabet, MassinissaMassinissaMerabetMAORE - Methods, Algorithms for Operations REsearch - LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - UM - Université de Montpellier - CNRS - Centre National de la Recherche ScientifiqueDurand, SylvainSylvainDurandMAORE - Methods, Algorithms for Operations REsearch - LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - UM - Université de Montpellier - CNRS - Centre National de la Recherche ScientifiqueMolnár, MiklósMiklósMolnárMAORE - Methods, Algorithms for Operations REsearch - LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - UM - Université de Montpellier - CNRS - Centre National de la Recherche ScientifiqueExact solution for bounded degree connected spanning problemsHAL CCSD2012spanning treehomomorphismedegree cosntraint[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]Gouat, Isabelle2012-10-26 11:48:382022-08-05 15:03:012012-10-29 14:13:13enReportsapplication/pdf1Given a connected edge-weighted graph G and a positive integer $R$, the Degree Constrained Minimum Spanning Tree problem (DCMST) consists in finding a minimum spanning tree of G such that the degree of each vertex in the tree is less than or equal to R. This problem, which has been extensively studied during the last four decades, has several practical applications, mainly in networks. However, some applications do not explicitly impose a sub-graph as solution. For this purpose, a more flexible structure called hierarchy is proposed. Hierarchies, which can be seen as a generalization of trees, are defined as a homomorphism of a tree in a graph. In this paper we study the Degree Constrained Minimum Spanning Hierarchy (DCMSH) problem. As DCMST, the DCMSH problem is also NP-hard. The first ILP formulation of this problem is given. Properties of the solution are analysed which allows to add valid inequalities to the ILP. To evaluate the difference of cost between trees and hierarchies, the exact solution of DCMST and DCMSH problems are compared. It appears from these comparisons that, in random spares graphs, the average percentage of improvement of the cost varied from 18% to 30% when the maximal authorized degree of vertices R is equal to 2, and from 8% to 22% when R equal to 3. The improvement increases as the graph size increases.