论文部分内容阅读
寻找出一个网络图的最小连通支配集有重要实际应用背景，然而如何找到它却是一个NP难题．本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集，该算法分为三个阶段：首先为顶点分配等级和生成顶点次序表，其次构造一个极大独立集，最后连接极大独立集中顶点．模拟实验表明该算法无论在运行时间和结果上都达到良好的效果．