Improving construction for connected dominating set with Steiner tree in wireless sensor networks

被引：90

作者：

Min, Manki ^{[1
]}

Du, Hongwei

Jia, Xiaohua

Huang, Christina Xiao

Huang, Scott C. -H.

Wu, Weili

机构：

[1] Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA

[2] City Univ Hong Kong, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China

[3] 3M Co, St Paul, MN 55144 USA

[4] Univ Texas, Dept Comp Sci, Richardson, TX 75083 USA

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2006年 / 35卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1007/s10898-005-8466-1

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The connected dominating set plays an important role in ad hoc wireless networking. Many constructions for approximating the minimum connected dominating set have been proposed in the literature. In this paper, we propose a new one with Steiner tree, which produces approximation solution within a factor of 6.8 from optimal. This approximation algorithm can also be implemented distributedly.

引用

页码：111 / 119

页数：9

共 18 条

[1]

[Anonymous], P 3 ACM INT S MOB AD

[2]

Bharghavan V., 1997, INT C COMM MONTR CAN

[3]

CADEI M, 2002, P 6 INT C COMP SCI I

[4] Approximations for Steiner trees with minimum number of Steiner points [J].

Chen, DG ;

Du, DZ ;

Hu, XD ;

Lin, GH ;

Wang, LS ;

Xue, GL .

JOURNAL OF GLOBAL OPTIMIZATION, 2000, 18 (01) :17-33

[5]

CHEN YP, 2002, P 3 ACM INT S MOB NE

[6] A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks [J].

Cheng, XZ ;

Huang, X ;

Li, DY ;

Wu, WL ;

Du, DZ .

NETWORKS, 2003, 42 (04) :202-208

[7]

DEERING S, 1994, P ACM SIGCOMM 1994 S

[8]

Du DZ, 2001, LECT NOTES COMPUT SC, V2108, P509

[9]

ERIKSSON H, 1994, COMMUNCICATIONS AUG

[10] Approximation algorithms for connected dominating sets [J].

Guha, S ;

Khuller, S .

ALGORITHMICA, 1998, 20 (04) :374-387

← 1 2 →