MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS

DOI10.1142/S0218195910003220zbMath1203.05106MaRDI QIDQ3562849

Sergey Bereg, Adrian Dumitrescu, Ming-Hui Jiang

Publication date: 28 May 2010

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmmaximum independent setdisk intersection graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Disjoint empty disks supported by a point set, On Covering Problems of Rado, Piercing translates and homothets of a convex body, Anchored rectangle and square packings, On covering problems of Rado, On the complexity of anchored rectangle packing, Systems of distant representatives in Euclidean space

Cites Work

• Increasing the minimum distance of a set of points
• Unit disk graphs
• Unsolved problems in geometry
• On the independence number of minimum distance graphs
• Independence numbers of planar contact graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Topics in Intersection Graph Theory
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs