Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03345800
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

File

molnarRR2021v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-03345800, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

8

Files downloads

2