论文部分内容阅读
简单无向图的最小连通支配集问题是NP完全问题，目前还没有成熟解法。提出了一种用有序袁构建独立集求解连通支配集的算法，算法从图中度最大的顶点开始将顶点加入到有序表中，并在加入过程中构建独立集，同时加入其他节点连接独立集使其成为连通集当图中所有节点处理完成，有序表中标记为独立集的节点和连接节点就形成了一个连通支配集。实验表明算法生成的支配集较小，运行时间复杂度比较低。