Broadcasting with the least energy is an NP-complete problem

Wuu Yang; Huei Ru Tseng; Rong Hong Jan; Bor Yeh Shen

doi:10.14257/ijmue.2008.3.3.06

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

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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 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 language	English
Pages (from-to)	55-66
Number of pages	12
Journal	International Journal of Multimedia and Ubiquitous Engineering
Volume	3
Issue number	3
DOIs	https://doi.org/10.14257/ijmue.2008.3.3.06
State	Published - 2008

Keywords

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

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.14257/ijmue.2008.3.3.06

Cite this

@article{df51705c509146589bc78e331cb6885b,

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 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.",

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",

doi = "10.14257/ijmue.2008.3.3.06",

language = "English",

volume = "3",

pages = "55--66",

journal = "International Journal of Multimedia and Ubiquitous Engineering",

issn = "1975-0080",

publisher = "Science and Engineering Research Support Society",

number = "3",

}

TY - JOUR

T1 - Broadcasting with the least energy is an NP-complete problem

AU - Yang, Wuu

AU - Tseng, Huei Ru

AU - Jan, Rong Hong

AU - Shen, Bor Yeh

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Graph theory

KW - Least-energy problem

KW - Maximum-leaf spanning- tree problem

KW - NP-complete

KW - Wireless network

UR - http://www.scopus.com/inward/record.url?scp=84863027155&partnerID=8YFLogxK

U2 - 10.14257/ijmue.2008.3.3.06

DO - 10.14257/ijmue.2008.3.3.06

M3 - Article

AN - SCOPUS:84863027155

SN - 1975-0080

VL - 3

SP - 55

EP - 66

JO - International Journal of Multimedia and Ubiquitous Engineering

JF - International Journal of Multimedia and Ubiquitous Engineering

IS - 3

ER -

Broadcasting with the least energy is an NP-complete problem

Abstract

Keywords

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this