Approximation algorithms for maximum independent set of a unit disk graph

DOI10.1016/J.IPL.2014.11.002MaRDI QIDQ483059zbMATH OpenOpenAlexFDO

Authors Gautam K. Das, Minati De, Sudeshna Kolay, Subhas C. Nandy, Susmita Sur-Kolay

Publication date 15 December 2014

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

Full work available at URL https://doi.org/10.1016/j.ipl.2014.11.002

zbMATH Keywords

approximation algorithmscomputational geometrymaximum independent setPTASunit disk graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Improved algorithm for maximum independent set on unit disk graph
• Efficient independent set approximation in unit disk graphs
• Faster approximation for maximum independent set on unit disk graph
• A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
• scientific article; zbMATH DE number 1507300

Cites work

• Algorithmic graph theory and perfect graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation schemes for covering and packing problems in image processing and VLSI
• scientific article; zbMATH DE number 5542232 (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?)
• scientific article; zbMATH DE number 2230206 (Why is no real title available?)
• Label placement by maximum independent set in rectangles
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Simple heuristics for unit disk graphs
• Unit disk graphs

Cited in

(14)

• Efficient independent set approximation in unit disk graphs
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• Faster approximation for maximum independent set on unit disk graph
• Approximation algorithms for independent sets in map graphs
• Improved algorithm for maximum independent set on unit disk graph
• A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Covering and packing of triangles intersecting a straight line
• Dominating set, independent set, discrete k-center, dispersion, and related problems for planar points in convex position
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

This page was built for publication: Approximation algorithms for maximum independent set of a unit disk graph

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