ALCOMFT-TR-02-144

Ioannis Caragiannis, Christos Kaklamanis and Panagiotis Kanellopoulos
New Results for Energy-Efficient Broadcasting in Wireless Networks
Patras. Work packages 2 and 4. December 2002.

Abstract: Motivated by the problem of supporting energy-efficient broadcasting in ad hoc wireless networks, we study the Minimum Energy Consumption Broadcast Subgraph (MECBS) problem. We present the first logarithmic approximation algorithm for the problem which uses an interesting reduction to Node-Weighted Connected Dominating Set. We also show that an important special instance of the problem can be solved in polynomial time, solving an open problem of Clementi et al.

Postscript file: ALCOMFT-TR-02-144.ps.gz (185 kb).