与えられた2部グラフからすべての完全な2部グラフを求める。

与えられた2部グラフで、すべての最大完全2部グラフをリストしたい。例えば与えられた2部グラフからすべての完全な2部グラフを求める。

、

頂点集合L = {A、B、C、D}

頂点集合R = {A、B、C、D、E}

エッジ：AA AB、Baの、BB、CC、CDやDC、Ddは、デ

最大の完全な二部は、次のとおり

{A、B} - {B}

{C、D} - {C、D}

{D} - {C、D、E}

をIは、ブルートフォースアルゴリズム、O（2^n）を発見しました。私はいくつかの近似アルゴリズムかランダム化されたアルゴリズムかどうかわかりません。

この問題はNP完全です。おおよその方法の問題は、プログラミング指向のCSコミュニティではなく、数学的または理論的CSコミュニティでよく聞かれます。 –

申し訳ありませんが、私は同じスレッドを数学コミュニティに投稿しますが、ここでは示唆しています。 – ColinBinWang

2部グラフの各部分の頂点のすべてのペアの間にエッジを追加することで、最大クリークを見つけることに問題を変えることができます。

Bron-Kerboschアルゴリズムを使用して、グラフ内のすべての最大クリークをリストすることができます（必ずしも2者ではない）。実装が非常に簡単で、O（3 ^（n/3））の最悪の場合のタイムバインディングが若干優れています。また、グラフの縮重の項で固定パラメータの扱いやすい時間境界があります。

2013-03-29 12:03:05

集合Aと集合Bを持ち、| A | > 1または| B | > 1は決してクリークにならない。 –

@ G.Bach、そうです。変換について言えば忘れて、編集を参照してください。 –

ああ私は、ええ、その作品を参照してください。 –

答えて