algorithme d'Edmonds pour les couplages

En informatique, plus précisément en théorie des graphes, l'algorithme d'Edmonds pour les couplages (blossom algorithm en anglais), aussi connu sous le nom d'algorithme des fleurs et des pétales est un algorithme pour construire des couplages maximaux sur les graphes. L'algorithme a été développé par Jack Edmonds en 1961, et publié en 1965. Étant donné un graphe quelconque G = (V, E), l'algorithme trouve un couplage M tel que chaque sommet de V est incident à au plus une arête dans E et M est de cardinal maximal. Le couplage est construit en améliorant itérativement un couplage vide initial le long de chemins augmentant dans le graphe. Contrairement au couplage biparti, ce couplage se base sur l'idée qu'un cycle de longueur impaire dans le graphe (fleur) est contracté en un seul sommet, la recherche se poursuivant de manière itérative dans le graphe contracté. L'algorithme a une complexité temporelle en , où est le nombre d'arêtes du graphe et est son nombre de sommets. L'algorithme de Micali et Vazirani permet de résoudre le même problème en , cependant il est beaucoup plus compliqué. Le blossom algorithm est historiquement important car il a donné la première preuve qu'un couplage maximal pouvait être trouvé en un temps polynomial, ce qui prouve que le problème de couplage maximal est dans la classe de complexité P.