Broadcasting with the least energy is an NP-complete problem

被引：0

作者：

Yang, Wuu ^{[1
]}

Tseng, Huei-Ru ^{[1
]}

Jan, Rong-Hong ^{[1
]}

Shen, Bor-Yeh ^{[1
]}

机构：

[1] Natl Chiao Tung Univ, Hsinchu, Taiwan

来源：

MUE: 2008 INTERNATIONAL CONFERENCE ON MULTIMEDIA AND UBIQUITOUS ENGINEERING, PROCEEDINGS | 2008年

关键词：

graph theory; least-energy problem; maximum-leaf spanning-tree problem; NP-complete; wireless network;

D O I：

10.1109/MUE.2008.48

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：197 / 200

页数：4

共 9 条

[1]

Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Gibbons A., 1985, ALGORITHMIC GRAPH TH

[3]

Oliveira C. A. S., 2004, Proceedings. 18th International Parallel and Distributed Processing Symposium

[4]

RAZZANO G, 2003, IEEE INT C COMM ICC, V2, P1096

[5]

Sheth A, 2003, 23RD INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS WORKSHOPS, P812

[6]

Solis-Oba R., 1998, LNCS, V1461, P441

[7]

TARJAN RE, 1983, DATA STRUCTURE NETWO

[8]

Tutte W., 1984, GRAPH THEORY

[9] Medium access control with coordinated adaptive sleeping for wireless sensor networks [J].

Ye, W ;

Heidemann, J ;

Estrin, D .

IEEE-ACM TRANSACTIONS ON NETWORKING, 2004, 12 (03) :493-506

← 1 →