Exact solution for bounded degree connected spanning problems

Massinissa Merabet 1 Sylvain Durand 1 Miklós Molnár 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Rapport
RR-12027, 2012
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00745713
Contributeur : Isabelle Gouat <>
Soumis le : vendredi 26 octobre 2012 - 11:48:38
Dernière modification le : mardi 23 janvier 2018 - 11:46:01
Document(s) archivé(s) le : dimanche 27 janvier 2013 - 03:40:13

Fichier

2008_tags_structures.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00745713, version 1

Collections

Citation

Massinissa Merabet, Sylvain Durand, Miklós Molnár. Exact solution for bounded degree connected spanning problems. RR-12027, 2012. 〈lirmm-00745713〉

Partager

Métriques

Consultations de la notice

148

Téléchargements de fichiers

547