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: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationProceedings - 2008 International Conference on Multimedia and Ubiquitous Engineering, MUE 2008
Pages197-200
Number of pages4
DOIs
StatePublished - 12 Sep 2008
Event2008 International Conference on Multimedia and Ubiquitous Engineering, MUE 2008 - Busan, Korea, Republic of
Duration: 24 Apr 200826 Apr 2008

Publication series

NameProceedings - 2008 International Conference on Multimedia and Ubiquitous Engineering, MUE 2008

Conference

Conference2008 International Conference on Multimedia and Ubiquitous Engineering, MUE 2008
CountryKorea, Republic of
CityBusan
Period24/04/0826/04/08

Keywords

  • 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