- INSTANCE:
A directed graph
, a set
consisting of all power levels at which a node can transmit, edge costs
, a source node
, an assignment operation
and some constant
.
- SOLUTION:
A node power assignment vector
inducing a directed graph
, where
, in which there is a path from
to any node of
(all nodes are covered)
- COST FUNCTION:
- OBJECTIVE:
Minimize cost, at most
*Approx.:*There exists approximation algorithm that achieves the approximation ratio [22].*Hardness:*NP-complete [22].*Comment:*There exists an approximation algorithm for the general version which achieves approximation ratio of .

2015-04-27 Revision: 288 PDF version