Abstract
We discuss the assignment of transmission ranges to the nodes of multi-hop
packet radio network (also known as static ad hoc wireless network) so
as to minimize the total energy while satisfying certain connectivity requirements.
These problems are known to be NP-Hard.
For symmetric connectivity (in which an edge is included when the transmission
ranges of both endpoints is large enough), we use algorithms designed for
the Steiner Tree problem to improve the approximation ratio from the previously
known 2 to 5/3 + epsilon.
For two connectivity, we mention a 4-approximation algorithm.
The symmetric connectivity result is joint work with Mandoiu and Zelikovsky
and appeared IFIP-TCS 2002. A preliminary version of the paper is available
at http://www.cs.iit.edu/~calinesc/.