Reports (Research Report) Year : 2022

Degree Constrained Minimum Spanning Hierarchies in Graphs under Non Uniform Capacity Constraints. Exact Solutions

Abstract

Degree constrained spanning tree problems are known and deeply analyzed when the graph nodes are provided with limited budgets. We examine the constrained spanning problem supposing heterogeneous degree bounds on nodes representing limited momentary capacities. In an undirected graph, different positive integer upper bounds are associated with nodes to limit their degree for each visit. The exact formulation of finding the minimum cost connected spanning structure satisfying these degree constraints is the subject of our work. The capacity constrained spanning problem with homogeneous constraints has been solved using spanning hierarchies which can be different from spanning trees. Here the case with non uniform constraints is analyzed, and we present an ILP based solution to this NP hard problem. The gain of applying hierarchies is demonstrated running ILPs for hierarchies and trees.
Fichier principal
Vignette du fichier
DCMSH_inh_molnar_v2.pdf (491.95 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03759534 , version 1 (26-08-2022)
lirmm-03759534 , version 2 (26-04-2023)

Identifiers

  • HAL Id : lirmm-03759534 , version 2

Cite

Miklós Molnár. Degree Constrained Minimum Spanning Hierarchies in Graphs under Non Uniform Capacity Constraints. Exact Solutions. [Research Report] LIRMM (UM, CNRS). 2022. ⟨lirmm-03759534v2⟩
83 View
55 Download

Share

More