Skip to Main content Skip to Navigation

Approximation of the Degree-Constrained Minimum Spanning Hierarchies

Miklós Molnár 1, * Sylvain Durand 1, 2 Massinissa Merabet 1 
* Corresponding author
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.
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Miklos Molnar Connect in order to contact the contributor
Submitted on : Wednesday, November 20, 2013 - 5:02:52 PM
Last modification on : Friday, October 22, 2021 - 3:07:29 PM
Long-term archiving on: : Friday, February 21, 2014 - 4:34:21 AM


Files produced by the author(s)


  • HAL Id : lirmm-00907052, version 1


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⟩



Record views


Files downloads