基于堆的最小连通支配集高效近似算法

• 作者: 张贵仓 杨海斌 赵学锋
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 最小连通支配集 堆 CDT算法
• 年，卷（期）: 2011,（2）
• 页码范围: 54-56
• 分类号: TP301.6
• 字数: 2994字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2011.02.019

摘要

提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法.利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造.通过计算堆操作次数,分析算法在平均情况下的时间复杂度.在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张贵仓	西北师范大学数学与信息科学学院	94	658	12.0	21.0
2	赵学锋	西北师范大学数学与信息科学学院	24	60	4.0	6.0
3	杨海斌	西北师范大学数学与信息科学学院	6	15	3.0	3.0