最小最大树划分的近似算法与最小和树划分的精确算法

• 作者: 农庆琴 原晋江
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 运筹学 划分 支撑树 多项式时间算法 近似算法
• 年，卷（期）: 2006,（4）
• 页码范围: 115-121
• 页数: 7页
• 分类号: O22
• 字数: 3910字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2006.04.014

摘要

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题).文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	原晋江	郑州大学数学系	26	97	6.0	7.0
2	农庆琴	郑州大学数学系	2	10	1.0	2.0