On the complexity of computing minimum energy consumption broadcast subgraphs
We consider the problem of computing an optimal range assignment in a wireless network which allows a specified source station to perform a broadcast operation. In particular, we consider this problem as a special case of the following more general combinatorial optimization problem, called Minimum Energy Consumption Broadcast Subgraph (in short, MECBS): Given a weighted directed graph and a specified source node, find a minimum cost range assignment to the nodes, whose corresponding transmission graph contains a spanning tree rooted at the source node. We first prove that MECBS is not approximable within a sub-logarithmic factor (unless P=NP). We then consider the restriction of MECBS to wireless networks and we prove several positive and negative results, depending on the geometric space dimension and on the distance-power gradient. The main result is a polynomial-time approximation algorithm for the NP-hard case in which both the dimension and the gradient are equal to 2: This algorithm can be generalized to the case in which the gradient is greater than or equal to the dimension. For the entire collection see [Zbl 0958.00036].
- An improved approximation algorithm for the minimum energy consumption broadcast subgraph
- New results for energy-efficient broadcasting in wireless networks
- A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem
- Minimum-energy broadcast and disk cover in grid wireless networks
- STACS 2004
- A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem
- The minimum broadcast range assignment problem on linear multi-hop wireless networks.
- An efficient approximation for minimum energy broadcast in multi-channel multi-hop wireless network with directional antennas
- Min-energy broadcast in mobile ad hoc networks with restricted motion
- A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks
- Fast neighbor lists for adaptive-resolution particle simulations
- The minimum k-storage problem on directed graphs
- Two new algorithms for the min-power broadcast problem in static ad hoc networks
- Improved approximation results for the minimum energy broadcasting problem
- On the approximability of the range assignment problem on radio networks in presence of selfish agents
- Optimal gossiping in geometric radio networks in the presence of dynamical faults
- Time-efficient broadcast in radio networks
- Energy consumption minimization in ad hoc wireless and multi-interface networks
- Time efficient k-shot broadcasting in known topology radio networks
- Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges
- Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks
- Improved Time Complexities of Algorithms for the Directional Minimum Energy Broadcast Problem
- New results for energy-efficient broadcasting in wireless networks
- An improved approximation algorithm for the minimum energy consumption broadcast subgraph
- Algorithmic Aspects of Minimum Energy Edge-Disjoint Paths in Wireless Networks
- The online broadcast range-assignment problem
- Connectivity guarantees for wireless networks with directional antennas
- Minimum energy broadcast on rectangular grid wireless networks
- Range assignment for energy efficient broadcasting in linear radio networks
- Minimum power assignment in wireless ad hoc networks with spanner property
- Sharing the cost of multicast transmissions in wireless networks
- Minimum-energy broadcast and disk cover in grid wireless networks
- On the complexity of minimizing interference in ad-hoc and sensor networks
- Minimum power multicasting problem in wireless networks
- Fast algorithm for multicast and data gathering in wireless networks
This page was built for publication: On the complexity of computing minimum energy consumption broadcast subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762500)