Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

ILP formulation of the degree-constrained minimum spanning hierarchy problem

Abstract : Given a connected edge-weighted graph G and a positive integer B, the degree-constrained minimum spanning tree problem (DCMST) consists in finding a minimum cost spanning tree of G such that the degree of each vertex in the tree is less than or equal to B. This problem, which has been extensively studied over the last few decades, has several practical applications, mainly in networks. However, some applications do not especially impose a subgraph as a solution. For this purpose, a more flexible so-called hierarchy structure has been proposed. Hierarchy, which can be seen as a generalization of trees, is defined as a homomorphism of a tree in a graph. In this paper, we discuss the degree-constrained minimum spanning hierarchy (DCMSH) problem which is NP-hard. An integer linear program (ILP) formulation of this new problem is given. Properties of the solution are analysed, which allows us to add valid inequalities to the ILP. To evaluate the difference of cost between trees and hierarchies, the exact solution of DCMST and z problems are compared. It appears that, in sparse random graphs, the average percentage of improvement of the cost varies from 20 to 36{\%} when the maximal authorized degree of vertices B is equal to 2, and from 11 to 31{\%} when B is equal to 3. The improvement increases as the graph size increases.
Complete list of metadata
Contributor : Miklos Molnar Connect in order to contact the contributor
Submitted on : Friday, April 16, 2021 - 2:45:39 PM
Last modification on : Tuesday, July 5, 2022 - 10:29:34 AM
Long-term archiving on: : Saturday, July 17, 2021 - 6:46:47 PM


Files produced by the author(s)



Massinissa Merabet, Miklós Molnár, Sylvain Durand. ILP formulation of the degree-constrained minimum spanning hierarchy problem. Journal of Combinatorial Optimization, Springer Verlag, 2018, 36 (3), pp.789-811. ⟨10.1007/s10878-017-0159-4⟩. ⟨lirmm-01584405⟩



Record views


Files downloads