IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i22p3521-d1518692.html
   My bibliography  Save this article

Degree-Constrained Steiner Problem in Graphs with Capacity Constraints

Author

Listed:
  • Miklos Molnar

    (LIRMM, University of Montpellier, CNRS, 161 rue Ada, 34095 Montpellier Cedex 5, France)

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.

Suggested Citation

  • Miklos Molnar, 2024. "Degree-Constrained Steiner Problem in Graphs with Capacity Constraints," Mathematics, MDPI, vol. 12(22), pages 1-16, November.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:22:p:3521-:d:1518692
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/22/3521/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/22/3521/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Cieslik, Dietmar, 2000. "The vertex degrees of minimum spanning trees," European Journal of Operational Research, Elsevier, vol. 125(2), pages 278-282, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Djauhari, Maman Abdurachman & Gan, Siew Lee, 2015. "Optimality problem of network topology in stocks market analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 108-114.
    2. Kazemilari, Mansooreh & Mardani, Abbas & Streimikiene, Dalia & Zavadskas, Edmundas Kazimieras, 2017. "An overview of renewable energy companies in stock exchange: Evidence from minimal spanning tree approach," Renewable Energy, Elsevier, vol. 102(PA), pages 107-117.
    3. Djauhari, Maman Abdurachman & Gan, Siew Lee, 2013. "Minimal spanning tree problem in stock networks analysis: An efficient algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 2226-2234.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:22:p:3521-:d:1518692. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.