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