Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/22/3521 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846153078361817088 |
|---|---|
| author | Miklos Molnar |
| author_facet | Miklos Molnar |
| author_sort | Miklos Molnar |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7ca4c06b437b4ab78063e30a53791dea |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-7ca4c06b437b4ab78063e30a53791dea2024-11-26T18:11:41ZengMDPI AGMathematics2227-73902024-11-011222352110.3390/math12223521Degree-Constrained Steiner Problem in Graphs with Capacity ConstraintsMiklos Molnar0LIRMM, University of Montpellier, CNRS, 161 rue Ada, 34095 Montpellier Cedex 5, FranceThe 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.https://www.mdpi.com/2227-7390/12/22/3521graph theorydegree-constrained Steiner treeSteiner hierarchyhomomorphismNP-hard problemexact computation |
| spellingShingle | Miklos Molnar Degree-Constrained Steiner Problem in Graphs with Capacity Constraints Mathematics graph theory degree-constrained Steiner tree Steiner hierarchy homomorphism NP-hard problem exact computation |
| title | Degree-Constrained Steiner Problem in Graphs with Capacity Constraints |
| title_full | Degree-Constrained Steiner Problem in Graphs with Capacity Constraints |
| title_fullStr | Degree-Constrained Steiner Problem in Graphs with Capacity Constraints |
| title_full_unstemmed | Degree-Constrained Steiner Problem in Graphs with Capacity Constraints |
| title_short | Degree-Constrained Steiner Problem in Graphs with Capacity Constraints |
| title_sort | degree constrained steiner problem in graphs with capacity constraints |
| topic | graph theory degree-constrained Steiner tree Steiner hierarchy homomorphism NP-hard problem exact computation |
| url | https://www.mdpi.com/2227-7390/12/22/3521 |
| work_keys_str_mv | AT miklosmolnar degreeconstrainedsteinerproblemingraphswithcapacityconstraints |