earticle

논문검색

Broadcasting with the least energy is an NP-complete problem

원문정보

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

보안공학연구지원센터(IJMUE) International Journal of Multimedia and Ubiquitous Engineering Vol.3 No.3 2008.07 pp.55-65
피인용수 : 0건 (자료제공 : 네이버학술정보)

초록

영어

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.

목차

Abstract
 1 Introduction
 2 Our Algorithm
  2.1 Practical Variations
  2.2 NP-Completeness of the Least-Energy Problem
 3 Conclusion
 References

키워드

저자정보

  • Wuu Yang National Chiao-Tung University, Taiwan, Republic of China
  • Huei-Ru Tseng National Chiao-Tung University, Taiwan, Republic of China
  • Rong-Hong Jan National Chiao-Tung University, Taiwan, Republic of China
  • Bor-Yeh Shen National Chiao-Tung University, Taiwan, Republic of China

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 원문제공기관과의 협약기간이 종료되어 열람이 제한될 수 있습니다.

      0개의 논문이 장바구니에 담겼습니다.