Dual Power Assignment via Second Hamiltonian Cycle

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from pi 2 6 − 136 + ≈ 1.617 to 117 ≈ 1.571. Moreover, we show that the algorithm of Khuller et al. [11] for the strongly con-nected spanning subgraph problem, which achieves an approximation ratio of 1.61, is 1.522-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results via utilizing interesting properties for the existence of a second Hamiltonian cycle.