Title :
Broadcasting with the Least Energy is an NP-Complete Problem
Author :
Yang, Wuu ; Tseng, Huei-Ru ; Jan, Rong-Hong ; Shen, Bor-Yeh
Author_Institution :
Nat. Chiao-Tung Univ., Hsinchu
Abstract :
Energy conservation is an important issue in wireless networks. We propose a method for estimating the least amount of energy needed for broadcasting a message to all nodes in the network. The method can work with any reasonable energy models. We prove that this least-energy problem is NP-complete by showing that the maximum-leaf spanning-tree problem is a special case of the least-energy problem.
Keywords :
computational complexity; radio broadcasting; radio networks; NP-complete problem; broadcasting; least-energy problem; maximum-leaf spanning-tree problem; wireless networks; Algorithm design and analysis; Batteries; Costs; Data communication; Digital multimedia broadcasting; Energy consumption; NP-complete problem; Power engineering and energy; Radio broadcasting; Wireless networks; NP-complete; graph theory; least-energy problem; maximum-leaf spanning-tree problem; wireless network;
Conference_Titel :
Multimedia and Ubiquitous Engineering, 2008. MUE 2008. International Conference on
Conference_Location :
Busan
Print_ISBN :
978-0-7695-3134-2
DOI :
10.1109/MUE.2008.48
