作者：武舒; 孔维祎; 孙坤; 郑建超连通支配集近似算法时间复杂度消息复杂度
摘要：针对在无线网络中构造连通支配集问题,提出了一种基于圆盘图模型构造连通支配集的分布式算法PS-CDS,算法分为2部分,首先由PS-CDS-1算法构造极大独立集,然后通过PS-CDS-2算法向极大独立集中添加连通节点得到连通支配集.所提出的算法包括功率分配方案,选择能完成邻域广播的最小发送功率.算法的时间复杂度为O(n),消息复杂度为O(nm ),近似比为R2T/R2min(2opt+1)-2.将PS-CDS算法与其他连通支配集算法进行实验比较,结果表明PS-CDS算法所生成的连通支配集规模最小.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
《曲阜师范大学学报·自然科学版》（CN：37-1154/N）是一本有较高学术价值的大型季刊，自创刊以来，选题新奇而不失报道广度，服务大众而不失理论高度。颇受业界和广大读者的关注和好评。 《曲阜师范大学学报·自然科学版》主要刊登数学、物理学、化学、生物学、体育、地理、相关的学科教育理论、科学方法论等方面的学术论文。其任务主要是反映自然科学方面的最新研究成果，促进国内外学术交流，为提高教学和科研水平服务。
杂志详情
