首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >对于这个图问题,有没有好的算法?

问对于这个图问题,有没有好的算法?
EN

Stack Overflow用户
提问于 2010-07-16 10:22:24
回答 1查看 599关注 0票数 4

有一个在边上有权的无向图(权是非负整数,它们的和不大,大多数是0)。我需要以最小化不同子图之间边的权重和的方式将其划分为若干个子图(假设20个节点的图到每个5个节点的4个子图)。

这听起来有点像最小割集问题,但还不够接近。

在另一种方案中-有一堆存储桶,所有的项目恰好属于两个存储桶,我需要将存储桶划分为存储桶组,以最小化多个存储桶组中的项目数量。(节点映射到存储桶,边权重映射到重复项目计数)

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2010-07-16 11:25:33

这是最小k-cut问题,是NP难问题。这是一个贪婪的启发式方法,可以保证2-1/k的近似值:

虽然图中的分量少于k个: 1)在每个分量中找到一个最小割集;2)拆分具有最小权重最小割集的分量。

本文研究的问题是:http://www.cc.gatech.edu/~vazirani/k-cut.ps

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/3261503

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档