Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs |
| |
Authors: | Gang Lu Ming-Tian Zhou Yong Tang Ming-Yuan Zhao Xin-Zheng Niu Kun She |
| |
Affiliation: | The authors are with School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, 610054, China. |
| |
Abstract: | The connected dominating set (CDS) problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs (UDGs). This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set (IS) in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones. |
| |
Keywords: | Approximation algorithm connected dominating set unit disk graph |
本文献已被 维普 万方数据 等数据库收录! |