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

Etant donne un graphe G = (V , E) et un entier k, le probleme Branch Vertices Constrained Minimum Spanning Hierarchy (BVCMSH) consiste en la recherche d'une hierarchie de recouvrement de poids minimum H de G ayant un nombre de sommets de branchements (sommets degre strictement superieur a deux) inferieur ou egal a k. Ce probleme etant NP-difficile, il ne peut exister d'algorithme efficace resolvant ce probleme de maniere 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 considerant le poids de l'arbre couvrant de poids minimum comme borne inferieure.