Degree Constrained Minimum Spanning Hierarchies in Graphs under Non Uniform Capacity Constraints. Exact Solutions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2022

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : lirmm-03759534 , version 2

Citer

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⟩
40 Consultations
32 Téléchargements

Partager

Gmail Facebook X LinkedIn More