文档名：区间图最小连通支配集问题的最优算法
摘要：针对区间图的最小连通支配集问题,设计简洁的线性算法.对该算法的时间、空间复杂度进行分析,并从实例和理论两方面验证其可行性和有效性.研究结果表明:该算法是线性的,即区间图上可在O(m+n)时间内找到一个最小连通支配集.
作者：周星宏 李鹏 王爱法 赵文平Author：ZHOUXinghong LIPeng WANGAifa ZHAOWenping
作者单位：重庆理工大学理学院,重庆400054
刊名：重庆理工大学学报 ISTICPKU
Journal：JournalofChongqingInstituteofTechnology
年，卷(期)：2023, 37(1)
分类号：O157.5
关键词：支配集问题 最小连通支配集问题 区间图 多项式算法 线性算法
机标分类号：TP301.6O223O157.5
在线出版日期：2023年3月7日
基金项目：国家自然科学基金，重庆市自然科学基金，重庆市教委科学技术研究计划项目，重庆市教委科学技术研究计划项目，重庆市教委科学技术研究计划项目，重庆市教委科学技术研究计划项目，重庆理工大学研究生教育高质量发展项目区间图最小连通支配集问题的最优算法[
期刊论文] 重庆理工大学学报--2023, 37(1)周星宏 李鹏 王爱法 赵文平针对区间图的最小连通支配集问题,设计简洁的线性算法.对该算法的时间、空间复杂度进行分析,并从实例和理论两方面验证其可行性和有效性.研究结果表明:该算法是线性的,即区间图上可在O(m+n)时间内找到一个最小连通支配集...参考文献和引证文献
参考文献
引证文献
本文读者也读过
相似文献
相关博文
区间图最小连通支配集问题的最优算法 An optimal algorithm for the minimum connected dominating set problem of interval graphs
区间图最小连通支配集问题的最优算法.pdf
- 文件大小:
- 1.05 MB
- 下载次数:
- 60
-
高速下载
|
|
