Degree-Constrained Steiner Problem in Graphs with Capacity Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Mathematics Année : 2024

Degree-Constrained Steiner Problem in Graphs with Capacity Constraints

Résumé

The degree-constrained Steiner problem in graphs is well known in the literature. In an undirected graph, positive integer degree bounds are associated with nodes and positive costs with the edges. The goal is to find the minimum cost tree spanning a given node set while respecting the degree bounds. As it is known, finding a tree satisfying the constraints is not always possible. The problem differs when the nodes can participate multiple times in the coverage and the constraints represent a limited degree (a capacity) for each occurrence of the nodes. The optimum corresponds to a graph-related structure, i.e., to a hierarchy. Finding the solution to this particular Steiner problem is NP-hard. We investigate the conditions of its existence and its exact computation. The gain of the hierarchies is demonstrated by solving ILPs to compute hierarchies and trees. The advantages of the spanning hierarchies are conclusive: (1) spanning hierarchies can be found in some cases where spanning trees matching the degree constraints do not exist; (2) the cost of the hierarchy can be lower even if the Steiner tree satisfying the constraints exists.
Fichier principal
Vignette du fichier
mathematics-12-03521-v2.pdf (312.15 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

lirmm-04825114 , version 1 (07-12-2024)

Licence

Identifiants

Citer

Miklos Molnar. Degree-Constrained Steiner Problem in Graphs with Capacity Constraints. Mathematics , 2024, 12 (22), pp.3521. ⟨10.3390/math12223521⟩. ⟨lirmm-04825114⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More