Problème de l'arbre de Steiner

Le problème de l'arbre de Steiner en informatique et théorie des graphes consiste à trouver un sous-graphe de poids minimal d'un graphe non orienté qui connecte un ensemble donné de sommets terminaux. L'objectif est de minimiser le poids total de toutes les arêtes du sous-graphe. Ce problème est NP-difficile, ce qui signifie que le calcul d'une solution optimale présente une complexité algorithmique élevée. Le problème de l'arbre de Steiner a des applications importantes dans des domaines tels que la conception de réseaux de communication et l'optimisation de la mise en page des circuits intégrés.