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

computational geometryapproximation algorithmsmaximum independent setPTASunit disk graph

Mathematics Subject Classification ID

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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
• Publication:4504025

Cites work

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

(13)

• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• Approximation algorithms for independent sets in map graphs
• Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
• Efficient independent set approximation in unit disk graphs
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• Covering and packing of triangles intersecting a straight line
• Improved algorithm for maximum independent set on unit disk graph
• 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
• 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: 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)