eine Korrespondenz maximaler Bewertung in einem bewerteten GraphenG.

Offenbar enthält eine solche Korrespondenz keine Kanten negativer Bewertung. Daher kann man sich bei diesem Problem auf Bewertungen ϱ : K(G) → ℝ mit ϱ(k) ≥ 0 zurückziehen. Auch unter dieser Voraussetzung muß aber eine maximale gewichtete Korrespondenz keineswegs eine Korrespondenz maximaler Mächtigkeit sein. Dies kann man aber dadurch erreichen, daß man G durch Hinzufügen fehlender Kanten k mit der Bewertung ϱ(k) = 0 zu einem vollständigen Graphen erweitert. Es sind polynomiale Algorithmen bekannt, die in einem bewerteten vollständigen Graphen maximale gewichtete Korrespondenzen liefern. Für den Spezialfall, daß G eine konstante Bewertung besitzt oder G ein bewerteter bipartiter Graph ist, siehe Edmonds, Algorithmus von, oder Ungarischer Algorithmus.