最小切割代价的限权树分割优化算法

• 作者: 彭凝多 秦科 罗光春 陈浩
• 来源期刊: 计算机应用研究
• 关键词: 树分割 动态规划 优化算法 分布式计算
• 年，卷（期）: 2014,（8）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2287-2289,2319
• 页数: 4页
• 分类号: TP301
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2014.08.010

摘要

研究一个在并行与分布式计算环境下兴起的树分割问题:给定一个节点和边均带权值的树T,通过切割树的边,将该树T分割成节点不相邻的子树,使得所有子树的节点权值之和不超过一个给定的上限K,并且使得被割边的权值之和最小.提出了一个能在多项式时间内完成的快速优化算法,包括一个基本的自底向上的结构及其动态规划方案和两个能大量节省计算空间的剪枝方案.实验表明,该算法在性能上相比其他同类算法要快十倍甚至数百倍,因而该算法能更好地应用于大规模并行任务调度的优化.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	秦科	电子科技大学计算机科学与工程学院	24	228	6.0	14.0
2	罗光春	电子科技大学计算机科学与工程学院	59	390	10.0	16.0
3	陈浩	电子科技大学计算机科学与工程学院	16	58	5.0	7.0
4	彭凝多	电子科技大学计算机科学与工程学院	6	27	3.0	5.0