Maximum area independent sets in disk intersection graphs

DOI10.1142/S0218195910003220MaRDI QIDQ3562849zbMATH OpenFDO

Authors Sergey Bereg, Adrian Dumitrescu, Minghui Jiang

Publication date 28 May 2010

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

Full work available at URL https://doi.org/10.1142/S0218195910003220

zbMATH Keywords

approximation algorithmdisk intersection graphmaximum independent set

Mathematics Subject Classification ID

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

Recommendations

• Approximation Algorithms for Geometric Intersection Graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for maximum independent set of pseudo-disks
• Graph-Theoretic Concepts in Computer Science
• Efficient independent set approximation in unit disk graphs

Cites work

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

Cited in

(8)

• Anchored rectangle and square packings
• Hardness results and approximation schemes for discrete packing and domination problems
• Systems of distant representatives in Euclidean space
• On Covering Problems of Rado
• Disjoint empty disks supported by a point set
• On the complexity of anchored rectangle packing
• Piercing translates and homothets of a convex body
• On covering problems of Rado

This page was built for publication: Maximum area independent sets in disk intersection graphs

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