標題: | Broadcasting with the least energy is an NP-complete problem |
作者: | Yang, Wuu Tseng, Huei-Ru Jan, Rong-Hong Shen, Bor-Yeh 交大名義發表 National Chiao Tung University |
關鍵字: | graph theory;least-energy problem;maximum-leaf spanning-tree problem;NP-complete;wireless network |
公開日期: | 2008 |
摘要: | 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. |
URI: | http://hdl.handle.net/11536/974 |
ISBN: | 978-0-7695-3134-2 |
期刊: | MUE: 2008 INTERNATIONAL CONFERENCE ON MULTIMEDIA AND UBIQUITOUS ENGINEERING, PROCEEDINGS |
起始頁: | 197 |
結束頁: | 200 |
Appears in Collections: | Conferences Paper |