HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

On the Approximation of Degree Constrained Spanning Problems in Graphs under Non Uniform Capacity Constraints

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 : In this study, the constrained spanning problem supposing heterogeneous degree bounds on nodes capacities representing limited momentary capacities is analyzed. Given an undirected graph, we suppose different positive integer upper bounds associated with nodes to limit their degree for each visit. Finding the minimum cost connected spanning structure satisfying the degree constraints is the subject of our work. Usually, for budget constrained problems spanning trees are the solutions and the problem is NP hard which can not be approximated by a constant factor. Moreover, spanning the nodes with a tree respecting the degree constraints is not always possible. We demonstrate that the optimal solution to solve the capacity limited spanning problem with heterogeneous bounds can be different from a spanning tree, and an earlier proposed generalization of the tree concept, i.e. the hierarchy corresponds to the minimum cost solution. We investigate on the degree constrained minimum spanning hierarchy (DCMSH) under non-uniform constraints, on the conditions of its existence and on the possibility of its approximation being the problem NP hard. We prove necessary and sufficient conditions to find spanning hierarchies corresponding to the constraints.
Document type :
Complete list of metadata

Contributor : Miklos Molnar Connect in order to contact the contributor
Submitted on : Sunday, October 31, 2021 - 8:51:57 PM
Last modification on : Saturday, November 6, 2021 - 4:21:06 AM


Files produced by the author(s)


  • HAL Id : lirmm-03345800, version 2



Miklós Molnár. On the Approximation of Degree Constrained Spanning Problems in Graphs under Non Uniform Capacity Constraints. [Research Report] LIRMM (UM, CNRS). 2021. ⟨lirmm-03345800v2⟩



Record views


Files downloads