Czy istnieje algorytm wielomianowy do znalezienia maksymalnego ważonego idealnego dopasowania na ogólnym wykresie?

Question

Widzę, że Blossom algorithm może być użyty do rozwiązania nieważonej wersji tego problemu i wiem, że ten problem może zostać zredukowany do problemu LP (ale z wykładniczą liczbą ograniczeń). Czy istnieje sposób rozwiązania tego problemu w czasie wielomianowym?

Answer 1

Tak, algorytm Blossom do obliczania maksymalnych nieważonych ogólnych dopasowań może być użyty w pierwotnym podwójnym algorytmie dla maksymalnych ważonych ogólnych dopasowań (jest to ogólna technika, węgierski algorytm jest dwustronnym odpowiednikiem). Istnieje implementacja o nazwie Blossom V ze względu na Władimira Kołmogorowa.