Saya tahu bahwa untuk grafik bipartit tanpa bobot, saya dapat menemukan penutup simpul minimum dengan terlebih dahulu menemukan pencocokan maksimum dan mengubahnya menjadi penutup simpul menggunakan Teorema König. Apakah ada modifikasi yang bisa digunakan jika node ditimbang?
ds.algorithms
graph-theory
Andrey Fedorov
sumber
sumber
Jawaban:
Masalah penutup simpul tertimbang dapat dirumuskan sebagai Program Integer (lihat http://en.wikipedia.org/wiki/Vertex_cover ). Ketika grafik input adalah bipartit, matriks kendala dari IP ini benar-benar unimodular. Oleh karena itu IP ini dapat diselesaikan dalam waktu polinomial.
Untuk detail lebih lanjut dari total matriks unimodular dan algoritma yang sesuai, lihat buku yang sangat baik (tiga volume) oleh Alexander Schrijver .
sumber