Solution exacte pour les problèmes de recouvrement sous contrainte sur le degré des noeuds

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
2 UM3 - Université Paul-Valéry - Montpellier 3
Résumé : Le problème de recherche d'arbre de recouvrement de coût minimum sous contrainte sur le degré des noeuds (Degree Constrained Minimum Spanning Tree ‐DCMST) est très étudié dans le domaine de la théorie des graphes et trouve son domaine d'application principalement dans les réseaux. La majorité des recherches sur les structures de recouvrement sous contrainte sur le degré des noeuds sont basées sur les arbres de recouvrement. Cependant, il existe des applications qui n'imposent pas explicitement un sous‐graphe comme solution. Une structure plus flexible appelée "hiérarchie" est proposée. Nous étudions le problème de la hiérarchie de recouvrement de coût minimum d'un graphe sous contrainte sur le degré des noeuds (Degree Constrained Minimum Spanning Hierarchy ‐DCMSH)
Type de document :
Communication dans un congrès
ROADEF: Recherche Opérationnelle et d'Aide à la Décision, Feb 2013, Troyes, France. 14e conférence de la société française de recherche opérationnelle et aide à la décision, 2013, 〈http://roadef2013.utt.fr/〉
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00805718
Contributeur : Sylvain Durand <>
Soumis le : jeudi 28 mars 2013 - 16:37:09
Dernière modification le : mardi 23 janvier 2018 - 11:46:01
Document(s) archivé(s) le : samedi 29 juin 2013 - 04:07:58

Fichier

exemple_ROADEF2013.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00805718, version 1

Collections

MAORE | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

Massinissa Merabet, Sylvain Durand, Miklós Molnár. Solution exacte pour les problèmes de recouvrement sous contrainte sur le degré des noeuds. ROADEF: Recherche Opérationnelle et d'Aide à la Décision, Feb 2013, Troyes, France. 14e conférence de la société française de recherche opérationnelle et aide à la décision, 2013, 〈http://roadef2013.utt.fr/〉. 〈lirmm-00805718〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

258

Téléchargements de fichiers

866

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD