Faster approximation for maximum independent set on unit disk graph

DOI10.1016/J.IPL.2017.07.007MaRDI QIDQ2398507zbMATH OpenOpenAlexFDO

Authors Subhas C. Nandy, Supantha Pandit, Sasanka Roy

Publication date 16 August 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.03260

zbMATH Keywords

dynamic programmingcomputational geometryapproximation algorithmsmaximum independent setunit disk graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: 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 [Jallu and Das 2016, Das et al. 2016].

Recommendations

• Improved algorithm for maximum independent set on unit disk graph
• Efficient independent set approximation in unit disk graphs
• Approximation algorithms for maximum independent set of a unit disk graph
• Publication:4504025
• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs

Cites work

• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• A study on two geometric location problems
• Approximation algorithms for maximum independent set of a unit disk graph
• Approximation schemes for covering and packing problems in image processing and VLSI
• Graph-Theoretic Concepts in Computer Science
• Improved algorithm for maximum independent set on unit disk graph
• Label placement by maximum independent set in rectangles
• Simple heuristics for unit disk graphs
• Unit disk graphs

Cited in

(8)

• Maximum bipartite subgraphs of geometric intersection graphs
• Efficient independent set approximation in unit disk graphs
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• Improved algorithm for maximum independent set on unit disk graph
• Approximation algorithms for maximum independent set of a unit disk graph
• Collision-free routing problem with restricted L-path
• Approximation algorithms for maximum independent set of pseudo-disks
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

This page was built for publication: Faster approximation for maximum independent set on unit disk graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2398507)