Approximation of the Degree-Constrained Minimum Spanning Hierarchies - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2014

Approximation of the Degree-Constrained Minimum Spanning Hierarchies

Abstract

Degree-constrained spanning problems are well known and are mainly used to solve capacity constrained routing problems. The degree-constrained spanning tree problems are NP-hard and computing the minimum cost spanning tree is not approximable. Often, applications (such as some degree-constrained 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 under constraints. This structure permits a new formulation of some degree-constrained spanning problems. In this paper we show that although the newly for- mulated problem is still NP-hard, it is approximable with a constant ratio. In the worst case, this ratio is bounded by 3/2. We provide a sim- ple heuristic and prove its approximation ratio is the best possible for any algorithm based on a minimum spanning tree.
Fichier principal
Vignette du fichier
s_molnar_19_01056259_app (1).pdf (164.78 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01056259 , version 1 (16-04-2021)

Identifiers

Cite

Miklós Molnár, Sylvain Durand, Massinissa Merabet. Approximation of the Degree-Constrained Minimum Spanning Hierarchies. 21th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), Jul 2014, Takayama, Japan. pp.96-107, ⟨10.1007/978-3-319-09620-9_9⟩. ⟨lirmm-01056259⟩
157 View
93 Download

Altmetric

Share

Gmail Facebook X LinkedIn More