基于最小生成树的连通支配集求解算法  

Novel connected dominating set algorithm based on minimum spanning tree

作　　者：高文宇[1] 

机构地区：[1]广东商学院信息学院,广州510320

出　　处：《计算机应用》2009年第6期1490-1493,共4页journal of Computer Applications

基　　金：广东省自然科学基金资助项目(8151032001000013)

摘　　要：针对无线网络中的连通支配集(CDS)问题,通过分析得到了CDS的一个重要性质,即简单连通无向图的最小CDS是该图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论,设计了一个新的连通支配集求解算法,实验表明,新算法较前人的算法有更好的性能。Through in-depth analysis, an important property of Connected Dominating Set （CDS） in wireless network was obtained, in which the smallest CDS of a simple connected graph is the non-leaf nodes of a spanning tree with most leaf nodes. A new CDS algorithm was designed on the basis of the analysis. Simulation results show that the algorithm possess better performance than others.

关 键 词：连通支配集 无线传感器网络 生成树算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]