A fast local search method for minimum energy broadcast in wireless ad hoc networks

Local search methods are often used to reduce the power consumption of broadcast routing in wireless networks. For a classic method, sweep, the best available time complexity result is O(|V|4). We present an O(|V|2)-time method, which exhaustively removes unnecessary transmissions yielding a solution comparable to that of sweep.