0

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

パーティションのバランスをうまく取りたいのですが、頂点の重みの合計がほぼ等しい必要があります。

良いアルゴリズムのアイデアはありますか？

4

2 に答える 2

0

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

于 2011-02-06T17:43:26.370 に答える
0

これは、一般にNP完全であり、対数因子近似アルゴリズムを備えた、ある種のバランスの取れたカット問題です。正しくない場合は、naveen gargによる2つの近似アルゴリズムを使用した平面グラフで弱くNPハードになります（googleでchk）

于 2011-04-08T18:30:13.033 に答える