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.
Type de document :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2017, pp.1-23. 〈10.1007/s10878-017-0159-4〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01584405
Contributeur : Miklos Molnar <>
Soumis le : vendredi 8 septembre 2017 - 16:52:31
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

Collections

Citation

Massinissa Merabet, Miklós Molnár, Sylvain Durand. ILP formulation of the degree-constrained minimum spanning hierarchy problem. Journal of Combinatorial Optimization, Springer Verlag, 2017, pp.1-23. 〈10.1007/s10878-017-0159-4〉. 〈lirmm-01584405〉

Partager

Métriques

Consultations de la notice

183