Skip to Main content Skip to Navigation
Reports

Exact solution for bounded degree connected spanning problems

Massinissa Merabet 1 Sylvain Durand 1 Miklós Molnár 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00745713
Contributor : Isabelle Gouat <>
Submitted on : Friday, October 26, 2012 - 11:48:38 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Sunday, January 27, 2013 - 3:40:13 AM

File

2008_tags_structures.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00745713, version 1

Collections

Citation

Massinissa Merabet, Sylvain Durand, Miklós Molnár. Exact solution for bounded degree connected spanning problems. RR-12027, 2012. ⟨lirmm-00745713⟩

Share

Metrics

Record views

227

Files downloads

736