ILP formulation of the degree-constrained minimum spanning hierarchy problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Combinatorial Optimization Year : 2018

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.
Fichier principal
Vignette du fichier
JOCO-V3_01584405_ILP.pdf (423.85 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01584405 , version 1 (16-04-2021)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More