0

给定一个具有顶点权重 W(V) 的无向循环平面图 G(V,E)、一个嵌入 E(G) 和两个节点 s 和 t 的固定平面，我需要找到 G 的一个分区，将其划分为两个连通分量S(G) 和 T(G)，其中 s 在 S(G) 中，t 在 T(G) 中。顶点 s 和 t 都属于嵌入 E(G) 中的外部面。

我希望分区能够很好地平衡 - 它们应该具有几乎相等的顶点权重之和。

请问有什么好的算法的想法吗？

4

2 回答 2

0

这是某种平衡切割问题，通常是 NP Complete 并且具有对数因子逼近算法。如果我是正确的，那么它在平面图中是弱 NP 困难的，由 naveen garg 提供 2 个近似算法。（在谷歌上查一下）

于 2011-04-08T18:30:13.033 回答
0

计算最小生成树并与 AVL 树平衡属性结合使用？

于 2011-02-06T17:43:26.370 回答