- INSTANCE:
A 4-tuple
where
is a simple graph,
is the source node,
are positive integers.
- SOLUTION:
A spanning broadcast tree rooted at
.
- COST FUNCTION:
Total energy in which each transmission radius is at most
.
- OBJECTIVE:
Minimize energy, at most
*Hardness:*NP-hard [44].*Comment:*Proof of NP-completeness of the Restricted Minimum-Energy Broadcast (RMEB) based on reduction from vertex cover problem to RMEB [44].

2015-04-27 Revision: 288 PDF version