Efficient independent set approximation in unit disk graphs

被引：2
作者：
Das, Gautam K. [1 ]
da Fonseca, Guilherme D. [2 ,3 ]
Jallu, Ramesh K. [1 ]
机构：
[1] Indian Inst Technol Guwahati, Dept Math, Gauhati, India
[2] Univ Auvergne, Clermont Ferrand, France
[3] LIMOS, Clermont Ferrand, France
来源：
DISCRETE APPLIED MATHEMATICS | 2020年 / 280卷
关键词：
Maximum independent set; Unit disk graph; Approximation algorithms; Polynomial time approximation scheme; ALGORITHMS; SCHEMES; PACKING; HARD;
D O I：
10.1016/j.dam.2018.05.049
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing polynomial-time approximation schemes motivated the development of faster constant approximation algorithms. In this paper, we present a 2.16-approximation algorithm that runs in O(nlog(2)n) time and a 2-approximation algorithm that runs in O(n(2) log n) time for the unweighted version of the problem. In the weighted version, the running times increase by an O(log n) factor. Our algorithms are based on a classic strip decomposition, but we improve over previous algorithms by efficiently using geometric data structures. We also propose a PTAS for the unweighted version. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：63 / 70
页数：8
相关论文
共 26 条
[1]   Label placement by maximum independent set in rectangles [J].
Agarwal, PK ;
van Kreveld, M ;
Suri, S .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 11 (3-4) :209-218
[2]  
[Anonymous], [No title captured]
[3]  
[Anonymous], [No title captured]
[4]   Tight Lower Bounds for Halfspace Range Searching [J].
Arya, Sunil ;
Mount, David M. ;
Xia, Jian .
DISCRETE & COMPUTATIONAL GEOMETRY, 2012, 47 (04) :711-730
[5]  
Bentley J.L., 1980, Journal of Algorithms, V1, P301
[6]   HOW HARD IS HALF-SPACE RANGE SEARCHING [J].
BRONNIMANN, H ;
CHAZELLE, B ;
PACH, J .
DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 10 (02) :143-155
[7]  
Carmi Paz, 2015, International Journal of Computational Geometry & Applications, V25, P227, DOI 10.1142/S0218195915500132
[8]   A Dynamic Data Structure for 3-d Convex Hulls and 2-d Nearest Neighbor Queries [J].
Chan, Timothy M. .
PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, :1196-1202
[9]   Approximation Algorithms for Maximum Independent Set of Pseudo-Disks [J].
Chan, Timothy M. ;
Har-Peled, Sariel .
DISCRETE & COMPUTATIONAL GEOMETRY, 2012, 48 (02) :373-392
[10]   Optimal Partition Trees [J].
Chan, Timothy M. .
DISCRETE & COMPUTATIONAL GEOMETRY, 2012, 47 (04) :661-690
123