loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 International Conference on Multimedia and Ubiquitous Engineering (mue 2008)
Broadcasting with the Least Energy is an NP-Complete Problem
April 24-April 26
ISBN: 978-0-7695-3134-2
ASCII Text
x 
 
Wuu Yang, Huei-Ru Tseng, Rong-Hong Jan, Bor-Yeh Shen, "Broadcasting with the Least Energy is an NP-Complete Problem," Multimedia and Ubiquitous Engineering, International Conference on, pp. 197-200, 2008 International Conference on Multimedia and Ubiquitous Engineering (mue 2008), 2008.
 
 
BibTex
x
 
@article{ 10.1109/MUE.2008.48,
author = {Wuu Yang and Huei-Ru Tseng and Rong-Hong Jan and Bor-Yeh Shen},
title = {Broadcasting with the Least Energy is an NP-Complete Problem},
journal ={Multimedia and Ubiquitous Engineering, International Conference on},
volume = {0},
year = {2008},
isbn = {978-0-7695-3134-2},
pages = {197-200},
doi = {http://doi.ieeecomputersociety.org/10.1109/MUE.2008.48},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Multimedia and Ubiquitous Engineering, International Conference on
TI - Broadcasting with the Least Energy is an NP-Complete Problem
SN - 978-0-7695-3134-2
SP197
EP200
A1 - Wuu Yang,
A1 - Huei-Ru Tseng,
A1 - Rong-Hong Jan,
A1 - Bor-Yeh Shen,
PY - 2008
KW - graph theory
KW - least-energy problem
KW - maximum-leaf spanning-tree problem
KW - NP-complete
KW - wireless network
VL - 0
JA - Multimedia and Ubiquitous Engineering, International Conference on
ER -
 
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.
Index Terms:
graph theory, least-energy problem, maximum-leaf spanning-tree problem, NP-complete, wireless network
Citation:
Wuu Yang, Huei-Ru Tseng, Rong-Hong Jan, Bor-Yeh Shen, "Broadcasting with the Least Energy is an NP-Complete Problem," mue, pp.197-200, 2008 International Conference on Multimedia and Ubiquitous Engineering (mue 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.