有一个在边上有权的无向图(权是非负整数,它们的和不大,大多数是0)。我需要以最小化不同子图之间边的权重和的方式将其划分为若干个子图(假设20个节点的图到每个5个节点的4个子图)。
这听起来有点像最小割集问题,但还不够接近。
在另一种方案中-有一堆存储桶,所有的项目恰好属于两个存储桶,我需要将存储桶划分为存储桶组,以最小化多个存储桶组中的项目数量。(节点映射到存储桶,边权重映射到重复项目计数)
发布于 2010-07-16 11:25:33
这是最小k-cut问题,是NP难问题。这是一个贪婪的启发式方法,可以保证2-1/k的近似值:
虽然图中的分量少于k个: 1)在每个分量中找到一个最小割集;2)拆分具有最小权重最小割集的分量。
https://stackoverflow.com/questions/3261503
复制相似问题