基于节点和边权重的图分区

Question

我有一个图G =（V，E），这两个边和节点都有权重。我想分割这个图来创建相同大小的分区。分区大小的定义是sum（vi）-sum（ej）其中vi是该分区内的节点，ej是该分区中两个节点之间的边缘。在我的问题中，图很密集（几乎完成）。有什么近似算法吗？

这在某种程度上类似于bin packing with overlapping objects中垃圾箱尺寸相同的问题。节点的重量是它们的大小和重量的边缘显示两个对象可以重叠多少。

Answer 1

我想如果你使用METIS程序解决了问题。 你可以下载这个链接的程序 http://glaros.dtc.umn.edu/gkhome/views/metis 它有一个很好的文档和非常快的程序。