Journal Articles Algorithms Year : 2024

Degree-Constrained Minimum Spanning Hierarchies in Graphs

Abstract

The minimum spanning tree problem in graphs under budget-type degree constraints (DCMST) is a well-known NP-hard problem. Spanning trees do not always exist, and the optimum can not be approximated within a constant factor. Recently, solutions have been proposed to solve degree-constrained spanning problems in the case of limited momentary capacities of the nodes. For a given node, the constraint represents a limited degree of the node for each visit. Finding the solution with minimum cost is NP-hard and the related algorithms are not trivial. This paper focuses on this new spanning problem with heterogeneous capacity-like degree bounds. The minimum cost solution corresponds to a graph-related structure, i.e., a hierarchy. We study the conditions of its existence, and we propose its exact computation, a heuristic algorithm, and its approximation.
Fichier principal
Vignette du fichier
algorithms-17-00467-v2.pdf (345) Télécharger le fichier
Origin Files produced by the author(s)
Licence

Dates and versions

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

Licence

Identifiers

Cite

Miklós Molnár. Degree-Constrained Minimum Spanning Hierarchies in Graphs. Algorithms, 2024, 17 (10), pp.467. ⟨10.3390/a17100467⟩. ⟨lirmm-04825111⟩
19 View
5 Download

Altmetric

Share

More