2

無向グラフに設定された最大独立頂点のメモリ保守的かつ効率的なアルゴリズムを見つけたいです。

従来のアルゴリズムは、補助データ構造 (元のグラフのコピー) を使用して実装します。リアルタイム実装ではメモリ割り当てが遅く、いくつかのメモリ境界があるため、このような並列構造は避けたいと思います。MIS のノードにブール値のラベルを付けたいだけです。出来ますか？

最大の独立集合ではなく、最大の独立集合が必要であることに注意してください。

PS この問題は言語に依存しないことはわかっていますが、C++ と STL でコーディングしています。

4

3 に答える 3

1

各ノード i にブール値のラベル (i) しかない場合の解決策を次に示します。|V| の場合、O(|V|+|E|) の時間がかかります。はノード数、|E| は 入力グラフのエッジの数です。

For all nodes v
   set label(v)=false;
For all nodes v
   if (all neighbors w of v have label(w)=false)
      set label(v)=true

label(v)=true のノード v は最大独立集合です。構造ごとに、ラベル付きノード v はラベル付き隣接ノードを持つことができないため、それらは独立しています。そして、それらは最大セットです。ラベルをアクティブにするだけで、ノード v をラベルなしのままにしておくのは、既にラベルが付けられた別の隣接 w がそれを妨げた場合のみです。

最適化の注意: ノードの番号が 1...n の場合、他の w は label(w)=true を持つことができないため、隣接する w=1..v-1 のみを確認する必要があります。

于 2012-05-30T15:23:58.643 に答える
0

スクラッチを使用するvectorかdeque<bool>、どの頂点が要素、エッジ、またはファセットで使用されているかを示すために使用します...

std::deque<bool> used(vertex.size(), false);
for (size_t e = 0; e < edge.size(); ++e)
{
    used[edge[e].v1] = true;
    used[edge[e].v2] = true;
}

Now used == true は、使用されているすべての頂点を示します。必要に応じて、他のものを折りたたむことができます。

于 2012-05-30T16:53:59.827 に答える
0

データ構造が何であるかを正確に知らずに、この種の質問に答えることは困難です。ほぼインプレースのグラフ操作の通常のトリックは、そうでなければゼロになる 2 つのビットをポインターから盗み出し、グラフ構造に可逆的な変更を加えることですが、それらがここでどのように適用されるかはわかりません。

あなたが書いたものを読むと、トラバーサルなしでグラフ内のノードを反復処理する方法がないようです。たとえば、DFS のスタックをどのように表現していますか?

于 2012-05-30T14:37:41.253 に答える