Coloring and Maximum Independent Set of Rectangles
From MaRDI portal
Publication:3088088
DOI10.1007/978-3-642-22935-0_11zbMath1343.90076MaRDI QIDQ3088088
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
Related Items
Unnamed Item, Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract), Outerstring Graphs are $\chi$-Bounded, Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded, On Guillotine Separability of Squares and Rectangles., Max point-tolerance graphs, Matching colored points with rectangles, Independent sets and hitting sets of bicolored rectangular families, Local boxicity, Improved algorithms for scheduling unsplittable flows on paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on maximum independent sets in rectangle intersection graphs
- Optimal packing and covering in the plane are NP-complete
- Label placement by maximum independent set in rectangles
- Fast stabbing of boxes in high dimensions
- Graph Theory and Probability
- On a Coloring Problem.
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Data Mining with optimized two-dimensional association rules
- Minimum Vertex Cover in Rectangle Graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Approximation algorithms for maximum independent set of pseudo-disks
- A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
- Intersection Graphs of Rectangles and Segments