Coloring and maximum independent set of rectangles

DOI10.1007/978-3-642-22935-0_11MaRDI QIDQ3088088zbMATH OpenOpenAlexFDO

Authors Parinya Chalermsook

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_11

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Maximum independent set of rectangles
• How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
• Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
• A note on maximum independent sets in rectangle intersection graphs
• Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs

Cites work

• A constant factor approximation algorithm for unsplittable flow on paths
• A note on maximum independent sets in rectangle intersection graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Data Mining with optimized two-dimensional association rules
• Fast stabbing of boxes in high dimensions
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Graph Theory and Probability
• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• scientific article; zbMATH DE number 1947059 (Why is no real title available?)
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• Improved approximation algorithms for rectangle tiling and packing.
• Intersection Graphs of Rectangles and Segments
• Label placement by maximum independent set in rectangles
• Minimum vertex cover in rectangle graphs
• On a Coloring Problem.
• Optimal packing and covering in the plane are NP-complete
• Polynomial-time approximation schemes for geometric graphs
• Polynomial-time approximation schemes for packing and piercing fat objects

Cited in

(12)

• Independent sets and hitting sets of bicolored rectangular families
• Local boxicity
• Improved algorithms for scheduling unsplittable flows on paths
• Max point-tolerance graphs
• Maximum independent set of rectangles
• Stochastic makespan minimization in structured set systems (extended abstract)
• Matching colored points with rectangles
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• Outerstring graphs are -bounded
• How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
• On Guillotine Separability of Squares and Rectangles.
• Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded

This page was built for publication: Coloring and maximum independent set of rectangles

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