Broadcasting with the least energy is an NP-complete problem

Wuu Yang*, Huei Ru Tseng, Rong Hong Jan, Bor Yeh Shen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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 mod- els. 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.

Original languageEnglish
Pages (from-to)55-66
Number of pages12
JournalInternational Journal of Multimedia and Ubiquitous Engineering
Issue number3
StatePublished - 1 Dec 2008


  • Graph theory
  • Least-energy problem
  • Maximum-leaf spanning- tree problem
  • NP-complete
  • Wireless network

Fingerprint Dive into the research topics of 'Broadcasting with the least energy is an NP-complete problem'. Together they form a unique fingerprint.

Cite this