| Affiliation: | (1) School of Computing and Department of Computer Science, Wuhan University and City University of Hong Kong, Hong Kong;(2) Department of Electrical and Computer Engineering, Indiana Uiversity Purdue University, Indianapolis, IN, 46202;(3) Department of Electrical Engineering and Computer Science, University of Toledo, Toledo;(4) Department of Computer Science, Illinois Institute of Technology, Chicago, IL, 60616;(5) Department of Computer Science, City University of Hong Kong, Hong Kong |
| Abstract: | The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k , a (k + 12H (k)) -approximation algorithm for k(2k–1)  n where n is the network size, a (k+2 (k + 1)/2 ) -approximation algorithm for 2 k7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.This work is supported in part by Hong Kong Research Grant Council under grant No. CityU 1149/04E.This work is partially supported by NSF CCR-0311174. |
