Dimitri Watel

Le problème de recherche d'un arbre couvrant avec un nombre minimum de noeuds de branchement (Minimum Branch Vertices ou MBV en anglais) consiste en la recherche, dans un graphe non orienté d'un arbre couvrant avec un nombre minimum de noeuds de degré 3 ou plus, appelés noeuds de branchements. Par exemple sur le graphe de droite, la solution optimale, dessinée en gras, consiste à choisir un arbre avec 1 noeuds de branchement, qui est au milieu à gauche. Tout comme la plupart des problèmes de couverture, ce problème s'applique notamment à la diffusion broadcast dans les réseaux de télécommunication, et plus particulièrement les réseaux de type tout-optique où duppliquer de l'information via des branchements est plus coûteux que dans un réseau électronique classique.

On s'est intéressé ici à plusieurs aspects du problème. En ce qui concerne son approximabilité, ce problème généralise la recherche d'une chaîne hamiltonienne dans un graphe, soit un arbre couvrant avec 0 noeuds de branchement, ce qui empêche toute recherche d'une solution optimale ou approchée en temps polynomial. En supposant que la solution optimale dispose d'au moins un noeud de branchement, le plus petit rapport d'approximation polynomial pour ce problème se situe entre log(n) et n. Nous avons également étudié sa complexité paramétrée vis-à-vis des paramètres faibles quand le graphe est peu dense: son nombre cyclomatique et le nombre de noeuds qui ne sont ni trivialement noeuds de branchement ni trivialement non noeuds de branchement dans une solution optimale. Enfin, nous étendons ces différentes études, quand elles ne mènent pas à des résultats théoriques utilisables en pratique à la recherche d'heuristiques efficaces pour ce problème.