liefert mit der Komplexität O(|E(G)|³) ein maximales Matching in einem Graphen G.

Dieser Algorithmus von U. Pape und D. Conradt aus dem Jahre 1980 stellt eine Modifizierung des Edmonds-Algorithmus’ (Edmonds, Algorithmus von) dar. Der wesentliche Unterschied besteht darin, daß Pape und Conradt die beim Algorithmus von Edmonds beschriebenen Kreise C ungerader Länge nicht zu einer Ecke zusammenziehen, sondern in zwei alternierende Wege aufspalten.