Un rapport d'approximation pour le problème de recherche de hiérarchie de recouvrement de poids minimum à branchements bornés

National audienceÉtant donné un graphe G = (V , E) et un entier k, le problème Branch Vertices Constrained Minimum Spanning Hierarchy (BVCMSH) consiste en la recherche d'une hiérarchie de recouvrement de poids minimum H de G ayant un nombre de sommets de branchements (sommets degré strictement supérieur à deux) inférieur ou égal à k. Ce problème étant NP-difficile, il ne peut exister d'algorithme efficace résolvant ce problème de manière exacte. Nous proposons dans ce papier un algorithme d'approximation polynomial ayant un ratio ρ = 2 · (1 − k |V |−1). Celui-ci est le meilleur possible en considérant le poids de l'arbre couvrant de poids minimum comme borne inférieure