Paper Info
Title
Approximation algorithms for maximum independent set of a unit disk graph.
Abstract
We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n3) and O(n2), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(nlog⁡n) time using O(n) space. We also propose a polynomial-time approximation scheme (PTAS) for the maximum independent set problem for a unit disk graph. Given an integer k>1, it produces a solution of size 1(1+1k)2|OPT| in O(k4nσklog⁡k+nlog⁡n) time and O(n+klog⁡k) space, where OPT is the subset of disks in an optimal solution and σk≤7k3+2. For a penny graph, the proposed PTAS produces a solution of size 1(1+1k)|OPT| in O(22σknk+nlog⁡n) time using O(2σk+n) space.
Year
DOI
Venue
2015
10.1016/j.ipl.2014.11.002
Information Processing Letters
Keywords
Field
DocType
Maximum independent set,Unit disk graph,Approximation algorithms,PTAS,Computational geometry
Integer,Discrete mathematics,Approximation algorithm,Graph,Combinatorics,Spacetime,Cubic graph,Computational geometry,Independent set,Mathematics,Unit disk graph
Journal
Volume
Issue
ISSN
115
3
0020-0190
Citations 
PageRank 
References 
6
0.46
11
Authors
5
Name
Order
Citations
PageRank
Gautam Das14083335.74
Minati De24510.11
Sudeshna Kolay360.46
Subhas C. Nandy428549.55
Susmita Sur-Kolay533339.50