Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs

被引：2

作者：

Zhang, Zhao ^{[1
]}

Lee, Joong-Lyul ^{[3
]}

Wu, Weili ^{[3
]}

Du, Ding-Zhu ^{[2
,3
]}

机构：

[1] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Zhejiang, Peoples R China

[2] Ton Duc Thang Univ, Fac Informat Technol, Div Algorithms & Technol Networks Anal, Ho Chi Minh City, Vietnam

[3] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA

来源：

OPTIMIZATION LETTERS | 2016年 / 10卷 / 07期

关键词：

Dominating and absorbing set; Strongly connected; Virtual backbone; Heterogeneous sensor networks; Approximation algorithm; Guaranteed performance; VIRTUAL BACKBONE CONSTRUCTION; WIRELESS SENSOR NETWORKS;

D O I：

10.1007/s11590-016-1007-7

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The strongly connected dominating and absorbing set (DAS) is used as a virtual backbone in heterogeneous wireless sensor. To reduce routing cost, we introduce a routing-cost constraint and study the problem of computing the minimum strongly connected DAS under routing-cost constraint. An approximation algorithm with guaranteed performance will be presented.

引用

页码：1393 / 1401

页数：9

共 20 条

[1]

[Anonymous], 1999, P 3 INT WORKSHOP DIS, DOI DOI 10.1145/313239.33261

[2]

[Anonymous], 1960, MATH Z, DOI DOI 10.1007/BF01159721

[3]

Bharghavan V., 1997, INT C COMM MONTR

[4] 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

[5]

Ding L., 2010, 30 INT C DISTR COMP, P448

[6] Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks [J].

Ding, Ling ;

Wu, Weili ;

Willson, James ;

Du, Hongjie ;

Lee, Wonjun ;

Du, Ding-Zhu .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2011, 22 (10) :1601-1609

[7] An exact algorithm for minimum CDS with shortest path constraint in wireless networks [J].

Ding, Ling ;

Gao, Xiaofeng ;

Wu, Weili ;

Lee, Wonjun ;

Zhu, Xu ;

Du, Ding-Zhu .

OPTIMIZATION LETTERS, 2011, 5 (02) :297-306

[8]

Du DZ, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P167

[9]

Du HW, 2011, IEEE INFOCOM SER, P1737, DOI 10.1109/INFCOM.2011.5934967

[10] CDS-Based Virtual Backbone Construction with Guaranteed Routing Cost in Wireless Sensor Networks [J].

Du, Hongwei ;

Wu, Weili ;

Ye, Qiang ;

Li, Deying ;

Lee, Wonjun ;

Xu, Xuepeng .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2013, 24 (04) :652-661

← 1 2 →