Exact solution for bounded degree connected spanning problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports Year : 2012

Exact solution for bounded degree connected spanning problems

Abstract

Given a connected edge-weighted graph G and a positive integer $R$, the Degree Constrained Minimum Spanning Tree problem (DCMST) consists in finding a minimum spanning tree of G such that the degree of each vertex in the tree is less than or equal to R. This problem, which has been extensively studied during the last four decades, has several practical applications, mainly in networks. However, some applications do not explicitly impose a sub-graph as solution. For this purpose, a more flexible structure called hierarchy is proposed. Hierarchies, which can be seen as a generalization of trees, are defined as a homomorphism of a tree in a graph. In this paper we study the Degree Constrained Minimum Spanning Hierarchy (DCMSH) problem. As DCMST, the DCMSH problem is also NP-hard. The first ILP formulation of this problem is given. Properties of the solution are analysed which allows to add valid inequalities to the ILP. To evaluate the difference of cost between trees and hierarchies, the exact solution of DCMST and DCMSH problems are compared. It appears from these comparisons that, in random spares graphs, the average percentage of improvement of the cost varied from 18% to 30% when the maximal authorized degree of vertices R is equal to 2, and from 8% to 22% when R equal to 3. The improvement increases as the graph size increases.
Fichier principal
Vignette du fichier
RR-Hiérarchie-LIRMM.pdf (344.47 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00745713 , version 1 (12-04-2024)

Identifiers

  • HAL Id : lirmm-00745713 , version 1

Cite

Massinissa Merabet, Sylvain Durand, Miklós Molnár. Exact solution for bounded degree connected spanning problems. RR-12027, LIRMM (UM, CNRS). 2012. ⟨lirmm-00745713⟩
166 View
494 Download

Share

More