algorithm - 二部グラフに設定された最大の独立頂点を見つけるためのブルートフォースアルゴリズム?

Question

二部グラフで設定された最大の独立頂点を見つけるための総当たりアルゴリズムの一般的な概要を知っている人はいますか?

MIS を見つけるためのケーニッヒの定理など、他のアルゴリズムがあることは知っていますが、ブルート フォース方式の疑似コードはどうなるのだろうと思っていました。

さらに、そのようなブルー​​ト フォース アルゴリズムの実行時の複雑さはどれくらいになるでしょうか?

Answer 1

ブルート フォース アルゴリズムは、頂点のすべてのセットを繰り返し処理し、それらが独立しているかどうかを確認するだけです。2^n頂点のセットがあり、独立性をチェックするためにすべてのエッジを反復処理すると、O(m)コストがかかりますO(2^n*m)。