Broadcasting with the least energy is an NP-complete problem

dc.citation.epage	200	en_US
dc.citation.spage	197	en_US
dc.contributor.author	Yang, Wuu	en_US
dc.contributor.author	Tseng, Huei-Ru	en_US
dc.contributor.author	Jan, Rong-Hong	en_US
dc.contributor.author	Shen, Bor-Yeh	en_US
dc.contributor.department	交大名義發表	zh_TW
dc.contributor.department	National Chiao Tung University	en_US
dc.date.accessioned	2014-12-08T15:02:17Z
dc.date.available	2014-12-08T15:02:17Z
dc.date.issued	2008	en_US
dc.description.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.	en_US
dc.identifier.isbn	978-0-7695-3134-2	en_US
dc.identifier.journal	MUE: 2008 INTERNATIONAL CONFERENCE ON MULTIMEDIA AND UBIQUITOUS ENGINEERING, PROCEEDINGS	en_US
dc.identifier.uri	https://ir.lib.nycu.edu.tw/handle/11536/974
dc.identifier.wosnumber	WOS:000256012200038
dc.language.iso	en_US	en_US
dc.subject	graph theory	en_US
dc.subject	least-energy problem	en_US
dc.subject	maximum-leaf spanning-tree problem	en_US
dc.subject	NP-complete	en_US
dc.subject	wireless network	en_US
dc.title	Broadcasting with the least energy is an NP-complete problem	en_US
dc.type	Proceedings Paper	en_US

Files

Now showing 1 - 1 of 1