Power assignment for k-connectivity in wireless ad hoc networks

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 >= 3, 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 <= k <= 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.