Type of publication: | Article |
Entered by: | |
Title | A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem |
Bibtex cite ID | RACTI-RU1-2003-42 |
Journal | Information Processing Letters |
Year published | 2003 |
Month | May |
Volume | 86 |
Number | 3 |
Pages | 149-154 |
DOI | 10.1016/s0020-0190(02)00484-2 |
Keywords | Graph algorithms; Approximation algorithms; Wireless networks |
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. |
Authors | |
Topics
| =SEE CLASSIFICATION DIFFERENCE FROM OTHERS=
=SEE OWN CLASSIFICATION=
|
BibTeX | BibTeX |
RIS | RIS |
Attachments | |
Publication ID | 571 |