graph - 基于节点和边权重的图划分

Question

我有一个图 G=(V,E) 边和节点都有权重。我想对该图进行分区以创建大小相等的分区。分区大小的定义是 sum(vi)-sum(ej)，其中 vi 是该分区内的一个节点，ej 是该分区内两个节点之间的一条边。在我的问题中，图表非常密集（几乎完整）。是否有任何近似算法？

这在某种程度上类似于 bin 包装中的问题，其中 bin 具有相同大小的重叠对象。节点的权重是它们的大小，边的权重显示两个对象可以重叠多少。

Answer 1

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