重庆理工大学学报2023，Vol.37Issue(1) ：309-314.DOI:10.3969/j.issn.1674-8425(z).2023.01.035

区间图最小连通支配集问题的最优算法

An optimal algorithm for the minimum connected dominating set problem of interval graphs

周星宏 李鹏 王爱法 赵文平
重庆理工大学学报2023，Vol.37Issue(1) ：309-314.DOI:10.3969/j.issn.1674-8425(z).2023.01.035
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 万方数据

区间图最小连通支配集问题的最优算法

An optimal algorithm for the minimum connected dominating set problem of interval graphs

周星宏 1李鹏 1王爱法 1赵文平1
扫码查看

作者信息

  • 1. 重庆理工大学 理学院,重庆 400054
  • 折叠

摘要

针对区间图的最小连通支配集问题,设计简洁的线性算法.对该算法的时间、空间复杂度进行分析,并从实例和理论两方面验证其可行性和有效性.研究结果表明:该算法是线性的,即区间图上可在O(m+n)时间内找到一个最小连通支配集.

关键词

支配集问题/最小连通支配集问题/区间图/多项式算法/线性算法

引用本文复制引用

基金项目

国家自然科学基金(11701059)

重庆市自然科学基金(cstc2020jcyjmsxmX0272)

重庆市教委科学技术研究计划项目(KJQN202001130)

重庆市教委科学技术研究计划项目(KJQN202101130)

重庆市教委科学技术研究计划项目(KJQN201801122)

重庆市教委科学技术研究计划项目(KJQN202001107)

重庆理工大学研究生教育高质量发展项目(gzlcx20223307)

出版年

2023
重庆理工大学学报
重庆理工大学

重庆理工大学学报

CSTPCD北大核心
影响因子：0.567
ISSN：1674-8425
参考文献量2
段落导航相关论文