| 无线网络中一种简单的弱连通支配集构造策略 |
| |
| 引用本文： | 王康,禹继国. 无线网络中一种简单的弱连通支配集构造策略[J]. 计算机工程与应用, 2011, 47(20): 81-84. DOI: 10.3778/j.issn.1002-8331.2011.20.024 |
| |
| 作者姓名： | 王康 禹继国 |
| |
| 作者单位： | 曲阜师范大学 计算机科学学院， 山东 日照 276826 |
| |
| 基金项目： | 国家自然科学基金，山东省中青年科学家奖励基金，山东省科技攻关计划，山东省教育厅科研项目 |
| |
| 摘 要： | 通过构造边支配集，提出了求解无线网络中弱连通支配集的集中式构造算法，该算法的时间复杂度为O（|N|+|E|）。同时在保证支配集的支配性和弱连通性不变的情况下，给出了两种修剪策略，以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性，并通过仿真验证了算法的有效性。与已有结果相比，该算法可以产生规模更小的弱连通支配集。
|
| 关 键 词： | 无线网络 弱连通支配集 边支配集 |
| 修稿时间： | |
Simple construction strategy for weakly connected dominating set in wireless networks |
| |
| WANG Kang,YU Jiguo. Simple construction strategy for weakly connected dominating set in wireless networks[J]. Computer Engineering and Applications, 2011, 47(20): 81-84. DOI: 10.3778/j.issn.1002-8331.2011.20.024 |
| |
| Authors: | WANG Kang YU Jiguo |
| |
| Affiliation: | Department of Computer Science，Qufu Normal University，Rizhao，Shandong 276826，China |
| |
| Abstract: | This paper proposes a central construction algorithm of weakly connected dominating sets in wireless networks by constructing edge dominating sets, simultaneously gives two pruning strategies to reduce the size of the produced set.The time complexity of the algorithm is O（｜N｜＋｜E｜）.It proves the correctness of the algorithm and shows the effectiveness of the algorithm.Compared to existed results,the algorithm proposed produces weakly dominating sets with smaller size. |
| |
| Keywords: | wireless networks weakly connected dominating set edge dominating set
|
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
