Exact solution for bounded degree connected spanning problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport Année : 2012

Exact solution for bounded degree connected spanning problems

Résumé

Given 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.
Fichier principal
Vignette du fichier
RR-Hiérarchie-LIRMM.pdf (344.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-00745713 , version 1 (12-04-2024)

Identifiants

  • HAL Id : lirmm-00745713 , version 1

Citer

Massinissa Merabet, Sylvain Durand, Miklós Molnár. Exact solution for bounded degree connected spanning problems. RR-12027, LIRMM (UM, CNRS). 2012. ⟨lirmm-00745713⟩
141 Consultations
487 Téléchargements

Partager

Gmail Facebook X LinkedIn More