A PTAS for minimum d-hop connected dominating set in growth-bounded graphs

被引：12

作者：

Gao, Xiaofeng ^{[1
]}

Wang, Wei ^{[2
]}

Zhang, Zhao ^{[3
]}

Zhu, Shiwei ^{[4
]}

Wu, Weili ^{[1
]}

机构：

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

[2] Xi An Jiao Tong Univ, Sch Sci, Xian 710049, Peoples R China

[3] Xinjiang Univ, Coll Math & Syst Sci, Xinjiang, Peoples R China

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

来源：

OPTIMIZATION LETTERS | 2010年 / 4卷 / 03期

关键词：

PTAS; Connected dominating set; Growth-bounded graph; WIRELESS NETWORKS; APPROXIMATION SCHEME;

D O I：

10.1007/s11590-009-0148-3

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we design the first polynomial time approximation scheme for d-hop connected dominating set (d-CDS) problem in growth-bounded graphs, which is a general type of graphs including unit disk graph, unit ball graph, etc. Such graphs can represent majority types of existing wireless networks. Our algorithm does not need geometric representation (e. g., specifying the positions of each node in the plane) beforehand. The main strategy is clustering partition. We select the d-CDS for each subset separately, union them together, and then connect the induced graph of this set. We also provide detailed performance and complexity analysis.

引用

页码：321 / 333

页数：13

共 50 条

[21] Greedy approximation for the minimum connected dominating set with labeling [J].

Yang, Zishen ;

Shi, Majun ;

Wang, Wei .

OPTIMIZATION LETTERS, 2021, 15 (02) :685-700

[22] Minimum connected dominating set and backbone of a random graph [J].

Habibulla, Yusupjan ;

Zhou, Hai-Jun .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2024, 2024 (06)

[23] Minimum Connected Dominating set for Certain Circulant Networks [J].

Parthiban, N. ;

Rajasingh, Indra ;

Rajan, R. Sundara .

3RD INTERNATIONAL CONFERENCE ON RECENT TRENDS IN COMPUTING 2015 (ICRTC-2015), 2015, 57 :587-591

[24] LOSSY KERNELS FOR CONNECTED DOMINATING SET ON SPARSE GRAPHS [J].

Eiben, Eduard ;

Kumar, Mithilesh ;

Mouawad, Amer E. ;

Panolan, Fahad ;

Siebertz, Sebastian .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) :1743-1771

[25] Lossy Kernels for Connected Dominating Set on Sparse Graphs [J].

Eiben, Eduard ;

Kumar, Mithilesh ;

Mouawad, Amer E. ;

Panolan, Fahad ;

Siebertz, Sebastian .

35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018), 2018, 96

[26] PTAS for the minimum k-path connected vertex cover problem in unit disk graphs [J].

Liu, Xianliang ;

Lu, Hongliang ;

Wang, Wei ;

Wu, Weili .

JOURNAL OF GLOBAL OPTIMIZATION, 2013, 56 (02) :449-458

[27] Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks [J].

Kim, Donghyun ;

Wu, Yiwei ;

Li, Yingshu ;

Zou, Feng ;

Du, Ding-Zhu .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2009, 20 (02) :147-157

[28] Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors [J].

Fomin, Fedor V. ;

Lokshtanov, Daniel ;

Saurabh, Saket ;

Thilikos, Dimitrios M. .

ACM TRANSACTIONS ON ALGORITHMS, 2018, 14 (01)

[29] Distributed construction of connected dominating set in unit disk graphs [J].

Jallu, Ramesh K. ;

Prasad, Prajwal R. ;

Das, Gautam K. .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2017, 104 :159-166

[30] Distributed Computation of Connected Dominating Set for Multi-hop Wireless Networks [J].

Surendran, Simi ;

Vijayan, Sreelakshmy .

6TH INTERNATIONAL CONFERENCE ON EMERGING UBIQUITOUS SYSTEMS AND PERVASIVE NETWORKS (EUSPN 2015)/THE 5TH INTERNATIONAL CONFERENCE ON CURRENT AND FUTURE TRENDS OF INFORMATION AND COMMUNICATION TECHNOLOGIES IN HEALTHCARE (ICTH-2015), 2015, 63 :482-487

← 1 2 3 4 5 →