Restricted Minimum-Energy Broadcast Problem

• INSTANCE: A 4-tuple $(G, s,d , K)$ where $G=(V,E)$ is a simple graph, $s \in V$ is the source node, $d < \vert V\vert, K < \vert V\vert^2$ are positive integers.

• SOLUTION: A spanning broadcast tree rooted at $s$ .

• COST FUNCTION: Total energy in which each transmission radius is at most $d$ .

• OBJECTIVE: Minimize energy, at most $K$

• 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].