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é.