A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem |
| |
| Authors: | Ioannis Caragiannis Christos Kaklamanis |
| |
| Affiliation: | Computer Technology Institute and Department of Computer Engineering and Informatics, University of Patras, 26500 Rio, Greece |
| |
| 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. |
| |
| Keywords: | Graph algorithms Approximation algorithms Wireless networks |
| 本文献已被 ScienceDirect 等数据库收录！ |
