Unrestricted Minimum-Energy Broadcast Problem

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

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

• COST FUNCTION: Total energy

• OBJECTIVE: Minimize energy, at most $K$

• Approx.: Optimal solution can be found within $O(n^{k+2})$ [44]