10.3969/j.issn.1000-3428.2011.02.019
基于堆的最小连通支配集高效近似算法
提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法.利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造.通过计算堆操作次数,分析算法在平均情况下的时间复杂度.在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集.
最小连通支配集、堆、CDT算法
37
TP301.6(计算技术、计算机技术)
甘肃省科技攻关计划基金资助项目2GS035-A052-011
2011-04-29(万方平台首次上网日期,不代表论文的发表时间)
共3页
54-56