Approximation algorithms for maximum independent set of a unit disk graph
A 2-factor approximation for computing the maximum independent set of unit disk graph is proposed. It runs in O(n3) O ( n 3 ) time and O(n2) O ( n 2 ) space. A similar technique works for penny graph in O(nlog?n) O ( n log ? n ) time and produces a 2-approximation result. Efficient PTAS are proposed for computing the maximum independent set of unit disk graph and penny graph.
approximation algorithms maximum independent set unit disk graph ptas computational geometry