Skip to Main content Skip to Navigation
Conference papers

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é.
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01584514
Contributor : Miklos Molnar <>
Submitted on : Friday, September 8, 2017 - 9:17:24 PM
Last modification on : Thursday, November 29, 2018 - 10:12:00 PM

File

MASSINISSA_MERABET_ROADEF2016....
Files produced by the author(s)

Identifiers

  • 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 Aide à la Décision, Feb 2017, Metz, France. ⟨lirmm-01584514⟩

Share

Metrics

Record views

164

Files downloads

80