Exact solution for branch vertices constrained spanning problems

Massinissa Merabet 1 Sylvain Durand 1, 2 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 graph G, a vertex v of G is said to be a branch vertex if its degree is strictly greater than 2. The Minimum Branch Vertices Spanning Tree problem (MBVST) consists in nding a spanning tree of G with the minimum number of branch vertices. This problem has been well studied in the literature and has several applications specially for routing in optical networks. However, this kind of applications do not explicitly impose a sub-graph as solution. A more flexible structure called hierarchy is proposed. Hierarchy, which can be seen as a generalization of trees, is de ned as a homomorphism of a tree in a graph. Since minimizing the number of branch vertices in a hierarchy does not make sense, we propose to search the minimum cost spanning hierarchy such that the number of branch vertices is less than or equal to an integer R. We introduce the Branch Vertices Constrained Minimum Spanning Hierarchy (BVCMSH) problem which is NP-hard. The Integer Linear Program (ILP) formulation of this new problem is given. To evaluate the di erence of cost between trees and hierarchies, we confront the BVCMSH problem to the Branch Vertices Constrained Minimum Spanning Tree (BVCMST) problem by comparing its exact solutions. It appears from this comparison that when R 2, the hierarchies improve the average cost from more than 8% when jVGj = 20 and from more than 12% when jVGj = 30.
Type de document :
Communication dans un congrès
INOC: International Network Optimization Conference, May 2013, Tenerife, Spain. 2013, 〈http://eventos.ull.es/inoc2013/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00826525
Contributeur : Sylvain Durand <>
Soumis le : lundi 27 mai 2013 - 16:30:46
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00826525, version 1

Collections

Citation

Massinissa Merabet, Sylvain Durand, Miklós Molnár. Exact solution for branch vertices constrained spanning problems. INOC: International Network Optimization Conference, May 2013, Tenerife, Spain. 2013, 〈http://eventos.ull.es/inoc2013/〉. 〈lirmm-00826525〉

Partager

Métriques

Consultations de la notice

142