计算树的[1,2]-数的算法研究

• 作者: 张超 赵承业
• 来源期刊: 中国计量学院学报
• 学科: 数学
• 关键词: [1,2]-数 0-1规划 贪婪策略 近似算法
• 年，卷（期）: 2015,（2）
• 所属期刊栏目: 数理科学
• 页码范围: 243-246
• 页数: 4页
• 分类号: O157.5
• 字数: 2729字
• 语种: 中文
• DOI: 10.3969/j.issn.1004-1540.2015.02.022

摘要

图G的一个点集S是[1,2]-集,若每个不在S中的点至少与S中的1个点相邻且至多与S中的2个点相邻.一个图的所有[1,2]-集中元素个数最小的集合,其元素个数称为图的[1,2]-数.针对树的[1,2]-数的计算问题进行研究.首先,根据[1,2]-数的定义给出了一个0-1规划模型,求解这个0-1规划可以得到图的[1,2]-数的精确值.然后,基于贪婪策略将树进行星分解,给出计算[1,2]-数的两个近似算法.最后,分析了两个近似算法的计算复杂度和性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张超	中国计量学院理学院	8	9	2.0	3.0
2	赵承业	中国计量学院理学院	7	10	2.0	3.0