Maximum area independent sets in disk intersection graphs
DOI10.1142/S0218195910003220zbMATH Open1203.05106MaRDI QIDQ3562849FDOQ3562849
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)
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
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Topics in Intersection Graph Theory
- Unit disk graphs
- Unsolved problems in geometry
- 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
- Increasing the minimum distance of a set of points
- On the independence number of minimum distance graphs
- Independence numbers of planar contact graphs
Cited In (8)
- On covering problems of Rado
- Systems of distant representatives in Euclidean space
- Hardness results and approximation schemes for discrete packing and domination problems
- On Covering Problems of Rado
- Piercing translates and homothets of a convex body
- Disjoint empty disks supported by a point set
- On the complexity of anchored rectangle packing
- Anchored rectangle and square packings
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)
