3

加重グラフ G=(V,E,w) を考えてみましょう。頂点 V_i のサブセットのファミリが与えられます。

シュタイナー フォレストは、頂点 V_i のサブセットごとに、このサブセット内のすべての頂点をツリーで接続するフォレストです。

例: V_1 = V の 1 つのサブセットのみ。この場合、シュタイナー フォレストはグラフ全体のスパニング ツリーです。

例: グラフ P4 (4 つの頂点を持つパス) と 2 つのサブセット: V_1 = {v1, v4} および V_2 = {v2, v3}。この例のシュタイナー木はグラフ全体です。

十分な理論。このような最小の重みを持つフォレストを見つけることは困難です (NP 完全)。このような最適でない重みを持つフォレストを見つけるためのより迅速な近似アルゴリズムを知っていますか?

4

2 に答える 2

4

Vijay Vazirani による「近似アルゴリズム」の第 20 章では、シュタイナー フォレストを生成するためのスキーマについて説明しています。分析では、アルゴリズムの因子を決定するために使用する LP 双対性を使用します。

(これは係数 2 のアルゴリズムですが、実際にはかなりうまくいく可能性があります)

近似アルゴリズム

また、トピックの調査を含む、さらに読むための 3 つの論文について説明している 22.5 の注を参照してください。

于 2010-04-20T18:04:26.077 に答える
0

たぶん、この問題を他の NP-complete として言い換えることができますか? ただし、これは推測にすぎません。私の非常に限られた数学スキルでは、そのようなマッピングを見つけることができません :)

于 2010-04-20T14:25:26.900 に答える