A New Formulation of Degree-Constrained Spanning Problems: (Extended Abstract)

Miklós Molnár 1 Sylvain Durand 1, 2 Massinissa Merabet 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 graph with edge-costs, searching for a minimum cost structure that connects a subset of vertices is a classic problem. We examine the spanning problems under constraints on the vertex degrees. Spanning tree solutions were generally investigated to solve them. However, for some applications the solution is not necessarily a sub-graph. Assuming that the degree constraint is due to the limited instantaneous capacity of the vertex and that the only other constraint on the spanning structure is its connectivity, we propose a reformulation of some spanning problems. To find the optimal coverage of the concerned vertices, an extension of the tree concept has been proposed. A hierarchy is obtained by a graph homomorphism between a tree and a target graph. Since this spanning structure may refer vertices (and edges) of the target graph several times, it is more flexible to satisfy constraints and nevertheless pertinent for network applications. Hierarchies correspond to the optimal solutions of the new problems. Here we resume our first promising results on the degree-constrained spanning hierarchies. They can solve network related cases where trees meeting the constraints do not exist. In other cases, hierarchies outperform trees. Furthermore, the degree constrained spanning hierarchy problem can be approximated within a constant ratio (while it is not possible with trees).
Type de document :
Communication dans un congrès
ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. 9th International Colloquium on Graph Theory and combinatorics, 2014, 〈http://oc.inpg.fr/conf/icgt2014/〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01065963
Contributeur : <>
Soumis le : jeudi 18 septembre 2014 - 17:49:53
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 19 décembre 2014 - 14:20:44

Fichier

resumeMolnar.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-01065963, version 1

Collections

Citation

Miklós Molnár, Sylvain Durand, Massinissa Merabet. A New Formulation of Degree-Constrained Spanning Problems: (Extended Abstract). ICGT: International Colloquium on Graph Theory and combinatorics, Jun 2014, Grenoble, France. 9th International Colloquium on Graph Theory and combinatorics, 2014, 〈http://oc.inpg.fr/conf/icgt2014/〉. 〈lirmm-01065963〉

Partager

Métriques

Consultations de la notice

211

Téléchargements de fichiers

335