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

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

作　　者：周星宏 李鹏 王爱法 赵文平 ZHOU Xinghong;LI Peng;WANG Aifa;ZHAO Wenping(College of Science,Chongqing University of Technology,Chongqing 400054,China)

机构地区：[1]重庆理工大学理学院,重庆400054

出　　处：《重庆理工大学学报（自然科学）》2023年第1期309-314,共6页Journal of Chongqing University of Technology：Natural Science

基　　金：国家自然科学基金项目(11701059);重庆市自然科学基金项目(cstc2020jcyj-msxmX0272);重庆市教委科学技术研究计划项目(KJQN202001130,KJQN202101130,KJQN201801122,KJQN202001107);重庆理工大学研究生教育高质量发展项目(gzlcx20223307)。

摘　　要：针对区间图的最小连通支配集问题,设计简洁的线性算法。对该算法的时间、空间复杂度进行分析,并从实例和理论两方面验证其可行性和有效性。研究结果表明:该算法是线性的,即区间图上可在O(m+n)时间内找到一个最小连通支配集。A simple linear algorithm is designed for the minimum connected dominating set problem of interval graphs. The time and space complexity of the algorithm is analyzed, and the feasibility and effectiveness of the algorithm are verified by cases and theory. The results show that the algorithm is linear, that is, a minimum connected dominating set found on the interval graph in O(m+n) time.

关 键 词：支配集问题 最小连通支配集问题 区间图 多项式算法 线性算法 

分 类 号：O157.5[理学—数学]