A note on maximum independent sets in rectangle intersection graphs

DOI10.1016/j.ipl.2003.09.019zbMath1178.68674MaRDI 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 programming; computational geometry; approximation algorithms

Mathematics Subject Classification ID

90C39: Dynamic programming

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W25: Approximation algorithms

Related Items

Approximation algorithms for free-label maximization, Approximation algorithms for maximum independent set of pseudo-disks, Minimum vertex cover in rectangle graphs, Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, Independent set of intersection graphs of convex objects in 2D, Coloring and Maximum Independent Set of Rectangles, DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION

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