k個のカットエッジ演算でグラフを最大化する

いくつかの重みを持つ N ノードを持つ無向グラフがあります。
M
のエッジがあり、グラフの接続されたコンポーネントのXOR合計を最大化したい正確にK 操作にあります。
((n1 XOR n2 XOR n3)+(c1 XOR c2 XOR c3))。
(2つのノードの間に複数のエッジが存在する可能性があります。

私はカットエッジを持つ最小スパニングツリーで試してみましたが、成功できませんでした。どんな助け?

ベストアンサー

私はこの問題はNP困難だと思います。

指定されたk個の頂点を区切る最小kカットを見つけることはNP困難です( https:
//en.wikipedia.org/wiki/Minimum_k-cut

)。したがって、k個の指定された頂点だけでなく、最小のk-cutインスタンスが与えられると、指定されたk個の頂点すべてに重み-1を割り当て、他の頂点に重み0を割り当てることができる。最後に、XOR問題のブラックボックスアルゴリズムを最小kカットサイズのバイナリ検索に適用します。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です