Approximation algorithms for maximum independent set of a unit disk graph

DOI10.1016/j.ipl.2014.11.002zbMath1317.68272OpenAlexW2034131445MaRDI QIDQ483059

Subhas C. Nandy, Minati De, Sudeshna Kolay, Gautam K. Das, 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

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

Related Items (7)

Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line ⋮ Faster approximation for maximum independent set on unit disk graph ⋮ Efficient independent set approximation in unit disk graphs ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Improved Algorithm for Maximum Independent Set on Unit Disk Graph ⋮ Covering and packing of triangles intersecting a straight line ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint

Cites Work

• Unit disk graphs
• Label placement by maximum independent set in rectangles
• Algorithmic graph theory and perfect graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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