Power assignment for k-connectivity in wireless ad hoc networks

Xiaohua Jia, Dongsoo Kim, Sam Makki, Peng Jun Wan, Tsi-Ui Ik

Research output: Contribution to journalArticlepeer-review

56 Scopus citations


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.

Original languageEnglish
Pages (from-to)213-222
Number of pages10
JournalJournal of Combinatorial Optimization
Issue number2
StatePublished - 1 Mar 2005


  • k-connectivity
  • Power assignment
  • Wireless ad hoc sensor networks

Fingerprint Dive into the research topics of 'Power assignment for k-connectivity in wireless ad hoc networks'. Together they form a unique fingerprint.

Cite this