@inproceedings{401b995709b04c9c845f657485846293,

title = "Broadcasting with the least energy is an NP-complete problem",

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 = "Graph theory, Least-energy problem, Maximum-leaf spanning-tree problem, NP-complete, Wireless network",

author = "Wuu Yang and Tseng, {Huei Ru} and Jan, {Rong Hong} and Shen, {Bor Yeh}",

year = "2008",

month = sep,

day = "12",

doi = "10.1109/MUE.2008.48",

language = "English",

isbn = "0769531342",

series = "Proceedings - 2008 International Conference on Multimedia and Ubiquitous Engineering, MUE 2008",

pages = "197--200",

booktitle = "Proceedings - 2008 International Conference on Multimedia and Ubiquitous Engineering, MUE 2008",

note = "null ; Conference date: 24-04-2008 Through 26-04-2008",

}