点赋权图上固定顶点的树划分问题

• 作者: 张同全
• 来源期刊: 云南民族大学学报（自然科学版）
• 学科: 数学
• 关键词: 反圈 启发式算法 导出子图 近似算法
• 年，卷（期）: 2007,（4）
• 页码范围: 303-305
• 页数: 3页
• 分类号: O157.5
• 字数: 2711字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-8513.2007.04.006

摘要

考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1/k近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张同全	云南民族大学数学与计算机科学学院	8	16	3.0	3.0