Упаковка вершин на двудольном графе

Question

Свяжите каждый узел неориентированного графа с положительным весом. Проблема упаковки вершин состоит в том, чтобы найти подмножество узлов с наибольшей суммой весов, чтобы не было выбрано двух узлов с ребром между ними.

Каков наиболее эффективный способ решения проблемы упаковки вершин для двудольного графа ? Я был в состоянии сформулировать это как проблему максимального потока с удвоенным количеством узлов. Есть ли более эффективный, возможно, прямой подход?

Answer 1

Ну, P - выполнимое решение проблемы упаковки вершин, если V-P - выполнимое решение проблемы покрытия вершин. Таким образом, максимальная упаковка вершин эквивалентна минимальному покрытию вершин. Минимальное покрытие вершин в свою очередь эквивалентно максимальному совпадению для двудольных графов.