Skip to Main content Skip to Navigation
Conference papers

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
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)
Document type :
Conference papers
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00805718
Contributor : Sylvain Durand <>
Submitted on : Thursday, March 28, 2013 - 4:37:09 PM
Last modification on : Thursday, June 10, 2021 - 5:07:00 PM
Long-term archiving on: : Saturday, June 29, 2013 - 4:07:58 AM

File

exemple_ROADEF2013.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00805718, version 1

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 Aide à la Décision, Feb 2013, Troyes, France. ⟨lirmm-00805718⟩

Share

Metrics

Record views

433

Files downloads

1284