请教关于graph partitioning的算法
登录 | 论坛导航 -> 华新鲜事 -> 求学狮城 | 本帖共有 2 楼，分 1 页, 当前显示第 1 页 : 本帖树形列表 : 刷新 : 返回上一页
<<始页　 [1]　 末页>>
作者：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版所有回复从这里展开收起列表
作者：PvsNP (等级：1 - 微不足道，发帖：291) 发表：2008-04-29 16:17:34　 2楼
[登录后回复]
在 Bird 的大作中提到：
with k=2, G=K_n, it is NP-completereduce PARTITION to it. FPT的算法肯定是有的。 如果treewidth is bounded，也是有快的算法的
谢谢！
欢迎来到华新中文网，踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
论坛导航 -> 华新鲜事 -> 求学狮城 | 返回上一页 | 本主题共有 2 篇文章，分 1 页, 当前显示第 1 页 | 回到顶部
<<始页　 [1]　 末页>>

请登录后回复：帐号 　 密码