(6+ε)-approximation for minimum weight dominating set in unit disk graphs

被引：0

作者：

Gao, Xiaofeng ^{[1
]}

Huang, Yaochun ^{[1
]}

Zhang, Zhao ^{[2
]}

Wu, Weili ^{[1
]}

机构：

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

[2] Xingjiang University, Coll Math & Syst Sci, Tin Shui Wai, Hong Kong, Peoples R China

来源：

COMPUTING AND COMBINATORICS, PROCEEDINGS | 2008年 / 5092卷

基金：

美国国家科学基金会;

关键词：

unit disk graph; approximation algorithm; dominating set;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It was a long-standing open problem whether the minimum weight dominating set in unit disk graphs has a polynomial-time constant-approximation. In 2006, Ambuhl et al solved this problem by presenting a 72-approximation for the minimum weight dominating set and also a 89-approximation for the minimum weight connected dominating set in unit disk graphs. In this paper, we improve their results by giving a (6 + epsilon)-approximation for the minimum weight dominating set and a (10 + epsilon)-approximation for the minimum weight connected dominating set in unit disk graphs where epsilon is any small positive number.

引用

页码：551 / +

页数：2

共 50 条

[31] A Study on the Minimum Dominating Set Problem Approximation in Parallel
Gambhir, Mahak
Kothapalli, Kishore
2017 TENTH INTERNATIONAL CONFERENCE ON CONTEMPORARY COMPUTING (IC3), 2017, : 13 - 18
[32] On minimum m-connected k-dominating set problem in unit disc graphs
Shang, Weiping
Yao, Frances
Wan, Pengjun
Hu, Xiaodong
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2008, 16 (02) : 99 - 106
[33] AN IMPROVED TWO-PHASED APPROXIMATION OF MINIMUM CONNECTED DOMINATING SETS IN UNIT DISK GRAPHS USING TWO-HOP DEGREE CENTRALITY
Zhao, Kun
Lu, Zheming
Nie, Tingyuan
Li, Yansheng
Song, Chuanwang
INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL, 2016, 12 (05): : 1553 - 1564
[34] Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
Zhang, Zhao
Lee, Joong-Lyul
Wu, Weili
Du, Ding-Zhu
OPTIMIZATION LETTERS, 2016, 10 (07) : 1393 - 1401
[35] Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
Zhao Zhang
Joong-Lyul Lee
Weili Wu
Ding-Zhu Du
Optimization Letters, 2016, 10 : 1393 - 1401
[36] A Better Constant Approximation for Minimum 3-connected m-dominating Set Problem in Unit Disk Graph using Tutte Decomposition
Wang, Wei
Liu, Bei
Kim, Donghyun
Li, Deying
Wang, Jingyi
Jiang, Yaolin
2015 IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (INFOCOM), 2015,
[37] Hybrid metaheuristic algorithms for minimum weight dominating set
Potluri, Anupama
Singh, Alok
APPLIED SOFT COMPUTING, 2013, 13 (01) : 76 - 88
[38] Brief Announcement: A LOCAL Constant Approximation Factor Algorithm for Minimum Dominating Set of Certain Planar Graphs
Alipour, Sharareh
Jafari, Amir
PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, : 501 - 502
[39] On Approximating Minimum 3-Connected m-Dominating Set Problem in Unit Disk Graph
Liu, Bei
Wang, Wei
Kim, Donghyun
Li, Deying
Wang, Jingyi
Tokuta, Alade O.
Jiang, Yaolin
IEEE-ACM TRANSACTIONS ON NETWORKING, 2016, 24 (05) : 2722 - 2733
[40] Minimum Clique Partition in Unit Disk Graphs
Dumitrescu, Adrian
Pach, Janos
GRAPHS AND COMBINATORICS, 2011, 27 (03) : 399 - 411

← 1 2 3 4 5 →