Approximation of the Degree-Constrained Minimum Spanning Hierarchies

Miklós Molnár 1, * Sylvain Durand 1, 2 Massinissa Merabet 1
* Auteur correspondant
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 : Degree-constrained spanning problems are well known and are mainly used to solve capacity constrained communication (routing) problems. The degree-constrained spanning tree problems are NP-hard and the minimum cost spanning tree is not approximable nor in the case where the entire graph must be spanned neither in partial spanning problems. Most of applications (such as communications) do not need trees as solutions. Recently, a more flexible, connected, graph related structure called hierarchy was proposed to span a set of vertices in the case of constraints. The application of this structure permit the reformulation of the degree-constrained spanning problem. In this paper we present not only the advantages of the new structure but also that the new and optimal structure is approximable with the help of fast polynomial algorithm. The obtained approximation ratio is very advantageous regarding the negative approximability results with spanning trees.
Type de document :
Rapport
[Research Report] RR-13035, LIRMM (UM, CNRS). 2013, pp.21
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00907052
Contributeur : <>
Soumis le : mercredi 20 novembre 2013 - 17:02:52
Dernière modification le : mardi 23 janvier 2018 - 11:46:01
Document(s) archivé(s) le : vendredi 21 février 2014 - 04:34:21

Fichier

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

Identifiants

  • HAL Id : lirmm-00907052, version 1

Collections

Citation

Miklós Molnár, Sylvain Durand, Massinissa Merabet. Approximation of the Degree-Constrained Minimum Spanning Hierarchies. [Research Report] RR-13035, LIRMM (UM, CNRS). 2013, pp.21. 〈lirmm-00907052〉

Partager

Métriques

Consultations de la notice

182

Téléchargements de fichiers

439