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

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

请教关于graph partitioning的算法如下图所示，图G上每个点v都有一个整数weight,给定整数k,怎样把G分成k个connected components,使得最大的component weight最小（component的weight即它所包含节点weight之和）。请问这个问题有没有什么经典的算法？多谢了！！ (more...)

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

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

这风却是年年都有

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

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