algorithme de poussage/réétiquetage

L'algorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau. Il a été publié par Goldberg et Tarjan en 1986. L'algorithme général a une complexité en temps en (ici est l'ensemble des sommets, et l'ensemble des arcs du graphe) ; une implémentation plus sophistiquée, utilisant une règle de sélection de sommets par pile a un temps d'exécution en ; une autre règle, celle qui sélectionne le sommet actif le plus élevé (dans un sens précisé plus loin) permet d'obtenir la complexité . Enfin l'implémentation avec une structure de données introduite par Daniel Sleator et Robert E. Tarjan et appelée arbre dynamique, et notamment avec un (en) donne un temps d'exécution majoré par . Tous ces temps sont meilleurs que la majoration en qui est celle de l'algorithme d'Edmonds-Karp.