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



请问这个问题有没有什么经典的算法？多谢了！！ [PvsNP (4-23 22:29, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

with k=2, G=K_n, it is NP-completereduce PARTITION to it.
FPT的算法肯定是有的。
如果treewidth is bounded，也是有快的算法的[Bird (4-25 19:22, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

(引用 Bird:with k=2, G=K_n, it is NP-completereduce PARTITION to it. FPT的算法肯定是有的。 如果treewidth is bounded，也是有快的算法的)谢谢！[PvsNP (4-29 16:17, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼