Lexikon der Mathematik: Pape-Conradt, Algorithmus von
liefert mit der Komplexität O(|E(G)|3) 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.
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!