重み付け無向グラフ分割

頂点重みW（V）、E（G）と2つのノードsおよびtを埋め込んだ固定平面の無向循環平面グラフG（V、E）が与えられた場合、GそれをS（G）にsを、T（G）にtをとった2つの連結成分S（G）とT（G）に分割する。頂点sとtは両方とも埋め込みE（G）の外面に属する。重み付け無向グラフ分割

私はパーティションのバランスが取れていることを望んでいます。頂点の重みの総和がほぼ同じである必要があります。

いいアルゴリズムのアイデアをお願いしますか？

2011-02-06 Isolin

一般的にNP完全であり、対数因子近似アルゴリズムを有するある種の平衡切断問題である。もし私が正しいならば、平面グラフの弱いNPであり、naveen gargによる2つのアルゴリズムを持つ。

2011-04-08 18:30:13 singhsumit

最小スパニングツリーを計算し、AVLツリーバランシングプロパティと組み合わせて使用しますか？

2011-02-06 17:43:26 James

スパニングツリーはバイナリではなく、頂点重みによる平衡のためのAVLの使用法は私には不明である。あなたのアイデアに関する詳細はありますか？しかし、私はむしろ混乱しています。 – Isolin

答えて