کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428897 | 686958 | 2015 | 8 صفحه PDF | دانلود رایگان |
• A 2-factor approximation for computing the maximum independent set of unit disk graph is proposed. It runs in O(n3)O(n3) time and O(n2)O(n2) space.
• A similar technique works for penny graph in O(nlogn)O(nlogn) time and produces a 2-approximation result.
• Efficient PTAS are proposed for computing the maximum independent set of unit disk graph and penny graph.
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)O(n3) and O(n2)O(n2), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(nlogn)O(nlogn) time using O(n)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>1k>1, it produces a solution of size 1(1+1k)2|OPT| in O(k4nσklogk+nlogn)O(k4nσklogk+nlogn) time and O(n+klogk)O(n+klogk) 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+nlogn)O(22σknk+nlogn) time using O(2σk+n)O(2σk+n) space.
Journal: Information Processing Letters - Volume 115, Issue 3, March 2015, Pages 439–446