华新 - 请教关于graph partitioning的算法

请教关于graph partitioning的算法

作者：PvsNP (等级：1 - 微不足道，发帖：291) 发表：2008-04-23 22:29:32　楼主　关注此帖评分：

请教关于graph partitioning的算法

如下图所示，图G上每个点v都有一个整数weight,给定整数k,怎样把G分成k个connected components,使得最大的component weight最小（component的weight即它所包含节点weight之和）。

请问这个问题有没有什么经典的算法？多谢了！！

欢迎来到华新中文网，踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版只看此人从这里展开收起列表

作者：Bird (等级：5 - 略有小成，发帖：759) 发表：2008-04-25 19:22:39　 2楼评分：

with k=2, G=K_n, it is NP-complete

reduce PARTITION to it.
FPT的算法肯定是有的。
如果treewidth is bounded，也是有快的算法的

欢迎来到华新中文网，踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版只看此人从这里展开收起列表

作者：PvsNP (等级：1 - 微不足道，发帖：291) 发表：2008-04-29 16:17:34　 3楼

with k=2, G=K_n, it is NP-completereduce PARTITION to it. FPT的算法肯定是有的。如果treewidth is bounded，也是有快的算法的

谢谢！

欢迎来到华新中文网，踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版只看此人从这里展开收起列表

论坛导航 -> 华新鲜事 -> 求学狮城 | 返回上一页 | 本主题共有 3 篇文章，分 1 页, 当前显示第 1 页 | 回到顶部
<<始页　 [1]　末页>>