The Budgeted Labeled Minimum Spanning Tree Problem

Raffaele Cerulli, Ciriaco D'Ambrosio, Domenico Serra and Carmine Sorgente ()
Additional contact information
Raffaele Cerulli: Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy
Ciriaco D'Ambrosio: Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy
Domenico Serra: Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy
Carmine Sorgente: Department of Mathematics, University of Salerno, 84084 Fisciano, SA, Italy

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

Abstract: In order to reduce complexity when designing multi-media communication networks, researchers often consider spanning tree problems defined on edge-labeled graphs. The earliest setting addressed in the literature aims to minimize the number of different media types, i.e., distinct labels, used in the network. Despite being extensively addressed, such a setting completely ignores edge costs. This led to the definition of more realistic versions, where budgets for the total cost, or the number of distinct labels allowed, were introduced. In this paper, we introduce and prove the NP-hardness of the Budgeted Labeled Minimum Spanning Tree problem, consisting in minimizing the cost of a spanning tree while satisfying specified budget constraints for each label type. This problem combines the challenges of cost efficiency and label diversity within a fixed budgetary framework, providing a more realistic and practical approach to network design. We provide three distinct mathematical programming formulations of the problem and design a Lagrangian approach to derive tighter lower bounds for the optimal solution of the problem. The performances of the proposed methods are assessed by conducting a series of computational experiments on a variety of randomly generated instances, which showed how the complexity of the problem increases as the size of the network, as well as the number of labels, increase and the budget restrictions are tightened.

Keywords: network design; minimum spanning tree; labeled graphs; integer linear programming (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/2/230/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/2/230/ (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:2:p:230-:d:1316787

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 ().