加权无向图划分
给定一个带有顶点权重 W(V) 的无向循环平面图 G(V,E)、一个嵌入 E(G) 的固定平面以及两个节点 s 和 t，我需要找到 G 的划分，将其分为两个连通分量S(G) 和 T(G)，其中 s 在 S(G) 中，t 在 T(G) 中。顶点 s 和 t 都属于嵌入 E(G) 中的外部面。
我希望分区能够很好地平衡 - 它们应该具有几乎相等的顶点权重总和。
请问有什么好的算法的想法吗？
Given an undirected cyclic planar graph G(V,E) with vertex weights W(V), a fixed plane embedding E(G) and two nodes s and t, I need to find a partitioning of G that divides it into two connected components S(G) and T(G) with s being in S(G) and t being in T(G). Vertices s and t both belong to the external face in the embedding E(G).
I wish to have the partitions well balanced - they should have nearly equal sums of vertex weights.
Any ideas for a good algorithm please?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
它是某种平衡切割问题，通常是 NP 完全问题，并且具有对数因子近似算法。如果我是正确的，那么它在平面图中是弱 NP 困难的，用 naveen garg 的 2 近似算法。（在 google 上查看它）
It is some sort of balanced cut problem which is NP Complete in general and has logarithmic factor approximation algorithms. If im correct then it is weakly NP hard in planar graphs with 2 approx algorithm by naveen garg.(chk it on google)
计算最小生成树并与 AVL 树平衡属性结合使用？
Compute a Minimum Spanning Tree and use in conjunction with an AVL Tree balancing properties?