Généralisation du problème de recherche d'arbre de recouvrement ayant un minimum de sommets de branchement - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2017

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

Abstract

É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é.
Fichier principal
Vignette du fichier
MASSINISSA_MERABET_ROADEF2016.pdf (301.63 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01584514 , version 1 (08-09-2017)

Identifiers

  • HAL Id : lirmm-01584514 , version 1

Cite

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 2017 - 18e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2017, Metz, France. ⟨lirmm-01584514⟩
123 View
74 Download

Share

Gmail Mastodon Facebook X LinkedIn More