Number of the records: 1
Improved Algorithm for Maximum Independent Set on Unit Disk Graph
- 1.
SYSNO ASEP 0534934 Document Type C - Proceedings Paper (int. conf.) R&D Document Type The record was not marked in the RIV Title Improved Algorithm for Maximum Independent Set on Unit Disk Graph Author(s) Jallu, Ramesh Kumar (UIVT-O) RID, ORCID, SAI
Das, G. K. (IN)Number of authors 2 Source Title Algorithmsand Discrete AppliedMathematics. - Cham : Springer, 2016 / Govindarajan S. ; Maheshwari A. - ISSN 0302-9743 - ISBN 978-3-319-29220-5 Pages s. 212-223 Action CADALM 2016. International Conference /2./ Event date 18.02.2016 - 20.02.2016 VEvent location Thiruvananthapuram Country IN - India Event type WRD Language eng - English Country CH - Switzerland Keywords time approximation schemes ; packing ; Maximum independent set ; Unit disk graph ; Approximation algorithm UT WOS 000376039500018 EID SCOPUS 84959101657 DOI 10.1007/978-3-319-29221-2_18 Annotation 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)]. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2021
Number of the records: 1