An exact algorithm for minimum CDS with shortest path constraint in wireless networks

被引：4

作者：

Ding, Ling ^{[1
]}

Gao, Xiaofeng ^{[1
]}

Wu, Weili ^{[1
]}

Lee, Wonjun ^{[2
]}

Zhu, Xu ^{[3
]}

Du, Ding-Zhu ^{[1
]}

机构：

[1] Univ Texas Dallas, Dept Comp Sci, Dallas, TX 75230 USA

[2] Korea Univ, Dept Comp Sci & Engn, Seoul, South Korea

[3] Xi An Jiao Tong Univ, Dept Math, Xian, Peoples R China

来源：

OPTIMIZATION LETTERS | 2011年 / 5卷 / 02期

基金：

美国国家科学基金会;

关键词：

CDS; Shortest path; Exact algorithm; CONNECTED DOMINATING SETS; UNIT DISK GRAPHS; APPROXIMATION; CONSTRUCTION;

D O I：

10.1007/s11590-010-0208-8

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(delta (2) n), where delta is the maximum node degree in communication graph.

引用

页码：297 / 306

页数：10

共 23 条

[1]

ALZOUBI K, 2002, P IEEE HICSS

[2]

[Anonymous], 1979, COMPUTERS INTRACTABI

[3]

BUTENKO S, 2001, P C COOP CONTR OPT

[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] Virtual backbone construction in multihop ad hoc wireless networks [J].

Cheng, XZ ;

Ding, M ;

Du, DH ;

Jia, XH .

WIRELESS COMMUNICATIONS & MOBILE COMPUTING, 2006, 6 (02) :183-190

[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] UNIT DISK GRAPHS [J].

CLARK, BN ;

COLBOURN, CJ ;

JOHNSON, DS .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :165-177

[8]

DAS B, 1997, P IEEE ICCC

[9]

Deb B., 2003, P IEEE INT WORKSH SE

[10]

Di W., 2006, P IEEE ICC

← 1 2 3 →