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

approximation algorithmscomputational geometrydynamic programmingmaximum independent setunit disk graph

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 1507300
• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs

Cites work

• 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
• 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?)
• 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)

• Collision-free routing problem with restricted L-path
• Efficient independent set approximation in unit disk graphs
• Improved algorithm for maximum independent set on unit disk graph
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• Approximation algorithms for maximum independent set of a unit disk graph
• Approximation algorithms for maximum independent set of pseudo-disks
• Maximum bipartite subgraphs of geometric intersection graphs
• 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)