计算机时代2023，Issue(5) ：51-56.DOI:10.16644/j.cnki.cn33-1094/tp.2023.05.011

奖励-收集顶点覆盖问题的精确算法

Exact algorithm for the prize-collecting vertex covering problem

曾宾 宁爱兵 付振星 徐江盼 张惠珍
计算机时代2023，Issue(5) ：51-56.DOI:10.16644/j.cnki.cn33-1094/tp.2023.05.011
✕
  • NETL
  • NSTL
  • 维普
  • 万方数据

奖励-收集顶点覆盖问题的精确算法

Exact algorithm for the prize-collecting vertex covering problem

曾宾 1宁爱兵 1付振星 1徐江盼 1张惠珍1
扫码查看

作者信息

  • 1. 上海理工大学管理学院,上海 200093
  • 折叠

摘要

奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题.本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法,通过降阶子算法可以降低该问题的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间.通过应用和算法对比表明,所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低.

关键词

奖励-收集顶点覆盖/上下界子算法/降阶子算法/回溯子算法

引用本文复制引用

基金项目

国家自然科学基金(71401106)

上海市"管理科学与工程"高原学科建设项目()

出版年

2023
计算机时代
浙江省计算技术研究所　浙江省计算机学会

计算机时代

影响因子：0.411
ISSN：1006-8228
参考文献量1
段落导航相关论文