Faster approximation for maximum independent set on unit disk graph

Maximum independent set from a given set D of unit disks intersecting a horizontal line can be solved in O (n(2)) time and O (n(2)) space. As a corollary, we design a factor 2 approximation algorithm for the maximum independent set problem on unit disk graph which takes both time and space of O (n(2)). The best known factor 2 approximation algorithm for this problem runs in O (n(2) logn) time and takes O (n(2)) space [1,2]. (C) 2017 Elsevier B.V. All rights reserved.