Généralisation du problème de recherche d'arbre de recouvrement ayant un minimum de sommets de branchement

Massinissa Merabet 1 Miklós Molnár 2
2 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é : Étant donné un graphe G = (V, E), un sommet de G est dit sommet de branchement s’il a un degré strictement supérieur à 2. Le problème NP-difficile et no-APX MBVST consiste à trouver un arbre de recouvrement de G ayant un minimum de sommets de branchement. Dans ce papier, nous introduisons le problème paramétré k-MBVST, où le paramètre k représente une limite de capacité.
Type de document :
Communication dans un congrès
ROADEF: Recherche Opérationnelle et d'Aide à la Décision, Feb 2017, Metz, France. 2017, ROADEF: Recherche Opérationnelle et d'Aide à la Décision, 2017
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01584514
Contributeur : Miklos Molnar <>
Soumis le : vendredi 8 septembre 2017 - 21:17:24
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

MASSINISSA_MERABET_ROADEF2016....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01584514, version 1

Collections

Citation

Massinissa Merabet, Miklós Molnár. Généralisation du problème de recherche d'arbre de recouvrement ayant un minimum de sommets de branchement. ROADEF: Recherche Opérationnelle et d'Aide à la Décision, Feb 2017, Metz, France. 2017, ROADEF: Recherche Opérationnelle et d'Aide à la Décision, 2017. 〈lirmm-01584514〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

15