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

扫码查看

原文链接

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

外文标题：An optimal algorithm for the minimum connected dominating set problem of interval graphs

作者：

周星宏、李鹏、王爱法、赵文平

展开 >

作者单位：

重庆理工大学理学院,重庆 400054

关键词：

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

基金：

国家自然科学基金重庆市自然科学基金重庆市教委科学技术研究计划项目重庆市教委科学技术研究计划项目重庆市教委科学技术研究计划项目重庆市教委科学技术研究计划项目重庆理工大学研究生教育高质量发展项目

项目编号：

11701059cstc2020jcyjmsxmX0272KJQN202001130KJQN202101130KJQN201801122KJQN202001107gzlcx20223307

出版年：

2023

DOI：

重庆理工大学学报

重庆理工大学

CSTPCD北大核心

影响因子：0.567

ISSN：1674-8425

年,卷(期)：2023.37(1)