Gibt es einen Polynomalgorithmus, um die maximale gewichtete perfekte Übereinstimmung in einem allgemeinen Diagramm zu finden?

Question

Ich sehe, dass Blossom algorithm kann verwendet werden, um die ungewichtete Version dieses Problems zu lösen, und ich weiß, dass dieses Problem auch auf ein LP-Problem reduziert werden kann (aber mit exponentiellen Anzahlen von Einschränkungen). Gibt es eine Möglichkeit, es in polynomieller Zeit zu lösen?

Answer 1

Ja, der Blossom-Algorithmus zur Berechnung maximaler ungewichteter allgemeiner Matchings kann in einem Primal-Dual-Algorithmus für maximal gewichtete allgemeine Matchings verwendet werden (dies ist eine allgemeine Technik; der ungarische Algorithmus ist das bipartite Äquivalent). Es gibt eine Implementierung, die wegen Vladimir Kolmogorov Blossom V genannt wird.