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

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

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


graph-theory mathematical-optimization np
person Petter    schedule 30.11.2011    source источник
comment
Задачу также называют максимальным (взвешенным) независимым множеством. Я должен был поискать немного больше, прежде чем спрашивать здесь.   -  person Petter    schedule 30.11.2011
comment
Рис. 4 в документе Инкрементное вычисление конвертов ресурсов в Producer -Потребительские модели кажутся более эффективными. Ваш ответ ниже, похоже, не работает для взвешенной версии этой проблемы.   -  person xuhdev    schedule 18.11.2017

Ответы (1)


arrow_upward
0
arrow_downward

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

person Petter    schedule 30.11.2011
comment
Можно поподробнее, как вы это сделали? как вы превращаете упаковку в обложку? и при чем здесь вес? Это решит последнюю проблему в stackoverflow.com/questions/14833281/ - person fons; 01.03.2013