Approximation of the Degree-Constrained Minimum Spanning Hierarchies - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports (Research Report) Year : 2013

Approximation of the Degree-Constrained Minimum Spanning Hierarchies


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.
Fichier principal
Vignette du fichier
dcmsh_approx.pdf (218.35 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00907052 , version 1 (20-11-2013)


  • 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⟩
244 View
856 Download


Gmail Facebook X LinkedIn More