Wiem, że dla nieważonego grafu dwustronnego mogę znaleźć minimalną osłonę wierzchołków, najpierw znajdując maksymalne dopasowanie i przekształcając ją w osłonę wierzchołków za pomocą Twierdzenia Königa. Czy istnieje modyfikacja, której można by użyć, gdyby węzły były ważone?
ds.algorithms
graph-theory
Andriej Fiodorow
źródło
źródło
Odpowiedzi:
Problem ważonej osłony wierzchołków można sformułować jako program liczb całkowitych (patrz http://en.wikipedia.org/wiki/Vertex_cover ). Gdy wykres wejściowy jest dwustronny, macierz ograniczeń tego adresu IP jest całkowicie niemodularna. Dlatego ten adres IP można rozwiązać w czasie wielomianowym.
Aby uzyskać więcej informacji na temat całkowitych niemodularnych matryc i odpowiadających im algorytmów, zobacz doskonałą (trzy tomową) książkę Aleksandra Schrijvera .
źródło