Degree-Constrained Steiner Problem in Graphs with Capacity Constraints

Miklos Molnar ()
Additional contact information
Miklos Molnar: LIRMM, University of Montpellier, CNRS, 161 rue Ada, 34095 Montpellier Cedex 5, France

Mathematics, 2024, vol. 12, issue 22, 1-16

Abstract: 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.

Keywords: graph theory; degree-constrained Steiner tree; Steiner hierarchy; homomorphism; NP-hard problem; exact computation; approximation (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/22/3521/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/22/3521/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:22:p:3521-:d:1518692

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().