私は最近この問題に遭遇しました。それが NP-Complete であるか、多項式時間で解けるかどうかを知りたいです。
加重二部グラフ G=(V,E) が与えられた場合、V は 2 つのセット A と B に分割でき、E は A と B を接続するエッジのセットです。エッジ (v,u) の重みは w( v、u)。
以下を順番に実行します。
- ノード v∈A を選び、
- (v,u)∈E ごとにすべてのノード u∈B を削除し、
- 削除されたすべてのエッジの合計スコアに重み w(v,u) を追加します。
目標は、合計スコアを最大化する一連のノード v1,…,vn∈A を見つけることです。
NP-Complete問題のバンクを検索して、この問題に還元できる可能性のあるものを見つけましたが、まだ有用なものは見つかりませんでした。どんな提案も非常に役に立ちます！