一种增量式约简方法求解最小顶点覆盖问题

• 作者: 占善华 谢小军
• 来源期刊: 计算机应用研究
• 关键词: 增量式约简 最小顶点覆盖 最小属性约简 大规模图
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3685-3688
• 页数: 4页
• 分类号: TP391.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2018.12.037

摘要

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法.首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间.实验结果表明了该算法的可行性和有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	占善华	广东司法警官职业学院信息管理系	11	11	2.0	2.0
2	谢小军	南京航空航天大学计算机科学与技术学院	2	0	0.0	0.0