请教关于graph partitioning的算法
所在版块：
求学狮城
发贴时间：2008-04-23 22:29
评分:
用户信息
昵称:
PvsNP
经验: 198
等级: 1 微不足道
资产:
380
华新币
发贴: 291
在线: 627.5 小时
复制本帖HTML代码
我要回复↙
相关跟贴↙
平板模式
手机浏览
下一跟贴
只看此人
本帖链接
字体:
小
中
大
高亮
:
今天贴
X
昨天贴
X
前天贴
X
如下图所示，图G上每个点v都有一个整数weight,给定整数k,怎样把G分成k个connected components,使得最大的component weight最小（component的weight即它所包含节点weight之和）。
请问这个问题有没有什么经典的算法？多谢了！！
.
欢迎来到华新中文网，踊跃发帖是支持我们的最好方法!
相关帖子
我要回复↙
↗回到正文
请教关于graph partitioning的算法
－
PvsNP
2008-04-23 22:29
(
290 bytes , 760reads
)
with k=2, G=K_n, it is NP-complete
－
Bird
2008-04-25 19:22
(
88 bytes , 500reads
)
谢谢！
－
PvsNP
2008-04-29 16:17
(
0 bytes , 326reads
)
－