Improved Algorithm for Maximum Independent Set on Unit Disk Graph

0534934 - ÚI 2021 CH eng C - Conference Paper (international conference)
Jallu, Ramesh Kumar - Das, G. K.
Improved Algorithm for Maximum Independent Set on Unit Disk Graph.
Algorithmsand Discrete AppliedMathematics. Cham: Springer, 2016 - (Govindarajan, S.; Maheshwari, A.), s. 212-223. Lecture Notes in Computer Science, 9602. ISBN 978-3-319-29220-5. ISSN 0302-9743.
[CADALM 2016. International Conference /2./. Thiruvananthapuram (IN), 18.02.2016-20.02.2016]
Keywords : time approximation schemes * packing * Maximum independent set * Unit disk graph * Approximation algorithm

In this paper, we present a 2-factor approximation algorithm for the maximum independent set problem on a unit disk graph, where the geometric representation of the graph has been given. We use dynamic programming and farthest point Voronoi diagram concept to achieve the desired approximation factor. Our algorithm runs in O(n(2) log n) time and O(n(2)) space, where n is the input size. We also propose a polynomial time approximation scheme (PTAS) for the same problem. Given a positive integer k, it can produce a solution of size 1/(1+ 1/k)(2) vertical bar OPT vertical bar in n O(k) time, where vertical bar OPT vertical bar is the optimum size of the solution. The best known algorithm available in the literature runs in (i) O(n(3)) time and O(n(2)) space for 2-factor approximation, and (ii) n(O(k log k)) time for PTAS [Das, G. K., De, M., Kolay, S., Nandy, S. C., Sur-Kolay, S.: Approximation algorithms for maximum independent set of a unit disk graph. Information Processing Letters 115(3), 439-446 (2015)].
Permanent Link: http://hdl.handle.net/11104/0313065