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

重庆理工大学学报（自然科学） ›› 2023, Vol. 37 ›› Issue (1): 309-314.

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

周星宏，李鹏，王爱法

重庆理工大学理学院，重庆４０００５

出版日期:2023-02-16 发布日期:2023-02-16
作者简介:周星宏，女，硕士研究生，主要从事图算法与区间图研究，Ｅｍａｉｌ：ｚ９７４２１８９３１＠１６３．ｃｏｍ；李鹏，男，博士，副教授，主要从事图与图算法研究，Ｅｍａｉｌ：ｌｉｐｅｎｇｃｑｕｔ＠ｃｑｕｔ．ｅｄｕ．ｃｎ。

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

Online:2023-02-16 Published:2023-02-16

摘要/Abstract

摘要： 针对区间图的最小连通支配集问题，设计简洁的线性算法。对该算法的时间、空间复杂度进行分析，并从实例和理论两方面验证其可行性和有效性。研究结果表明：该算法是线性的，即区间图上可在Ｏ（ｍ＋ｎ）时间内找到一个最小连通支配集。

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

Abstract: 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

周星宏, 李鹏, 王爱法. 区间图最小连通支配集问题的最优算法[J]. 重庆理工大学学报（自然科学）, 2023, 37(1): 309-314.

[1]	葛姝媛, 原军. 交错群图的混合故障诊断问题研究[J]. 重庆理工大学学报（自然科学）, 2023, 37(1): 302-308.
[2]	刘梦甜, 梅银珍, 高玉斌. 一些特殊图的算术-几何能量[J]. 重庆理工大学学报（自然科学）, 2020, 34(11): 263-268.
[3]	熊河浪，张华. 非均匀Ｋｕｒａｍｏｔｏ振子系统的频率同步[J]. 重庆理工大学学报（自然科学）, 2021, 35(8): 230-236.
[4]	张智微，李鹏. 边赋权简单图最长圈问题研究[J]. 重庆理工大学学报（自然科学）, 2021, 35(9): 220-226.
[5]	王猗，高玉斌. 图的算数－几何谱半径及能量的界[J]. 重庆理工大学学报（自然科学）, 2021, 35(9): 227-231.