Abstract FR:

Nous avons decrit les mecanismes de base, et les calculs de complexite amortie des principales structures de donnees de type files de priorite (tas de fibonnaci, tas relaches et tas apparies). Nous apportons plusieurs variantes aux tas apparies et etendons les tas de fibonacci a l'operation de difference symetrique (tas de fibonacci redondants). Nous avons experimente comparativement ces differents tas, au sein d'algorithmes combinatoires tels que la recherche d'arbres de poids minimum. A l'aide des files de priorite nous avons elabore un algorithme d'enumeration ordonnee des k arbres de poids minimum d'un graphe. Il comporte plusieurs variantes selon la densite ou la fonction de poids des aretes du graphe. Nous avons applique ces structures a la construction d'un algorithme de resolution exacte du probleme de steiner dans les graphes, par reduction puis enumeration. La premiere phase regroupe les principaux tests de reduction (inclusion ou elimination d'aretes et de sommets) connus a ce jour, en abaissant la complexite de leur application. La deuxieme phase utilise l'algorithme d'enumeration ordonnee pour rechercher un arbre de steiner solution. Notre approche permet de trouver une solution exacte pour des graphes meme denses comportant plusieurs centaines de sommets, quand la proportion de sommets imposes est importante. Les bornes inferieures et superieures calculees au cours de l'enumeration offrent des garanties de performance pour les solutions approchees construites