A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem
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. (C) 2003 Elsevier Science B.V. All rights reserved.
approximation algorithms wireless networks graph algorithms