A note on maximum independent sets in rectangle intersection graphs

DOI10.1016/j.ipl.2003.09.019zbMath1178.68674OpenAlexW2155875791MaRDI QIDQ1029038

Timothy M. Chan

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.09.019

zbMATH Keywords

dynamic programmingcomputational geometryapproximation algorithms

Mathematics Subject Classification ID

Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (14)

Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract) ⋮ Approximation algorithms on consistent dynamic map labeling ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ Keep your distance: land division with separation ⋮ Approximation algorithms for free-label maximization ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Matching colored points with rectangles ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Minimum vertex cover in rectangle graphs ⋮ Coloring and Maximum Independent Set of Rectangles ⋮ DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION ⋮ On the stab number of rectangle intersection graphs ⋮ Stochastic makespan minimization in structured set systems

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal packing and covering in the plane are NP-complete
• Label placement by maximum independent set in rectangles
• Iterated nearest neighbors and finding minimal polytopes
• Fast stabbing of boxes in high dimensions
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Approximation schemes for covering and packing problems in image processing and VLSI
• Polynomial-time approximation schemes for packing and piercing fat objects

This page was built for publication: A note on maximum independent sets in rectangle intersection graphs