Approximation algorithms for maximum independent set of a unit disk graph

作者：Das Gautam K; De Minati; Kolay Sudeshna; Nandy Subhas C^*; Sur Kolay Susmita

来源：Information Processing Letters, 2015, 115(3): 439-446.

DOI：10.1016/j.ipl.2014.11.002

• Maximum independent set
• Unit disk graph
• Approximation algorithms
• PTAS
• Computational geometry

We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n(3)) and O(n(2)), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(n logn) 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+1/k)(2) vertical bar OPT vertical bar in O(k(4)n(sigma k) (logk) + nlogn) time and O(n + klogk) space, where OPT is the subset of disks in an optimal solution and ak sigma k <= 2. For a penny graph, the proposed PTAS produces a solution of size 1/(1+1/k) vertical bar OPT vertical bar in O(2(2 sigma k)nk + nlogn) time using O(2(2 sigma k)+n) space.

• 出版日期2015-3