Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
DOI10.1145/2261250.2261293zbMATH Open1293.05101OpenAlexW1994213977MaRDI QIDQ2874591FDOQ2874591
Authors: Timothy M. Chan 
Publication date: 7 August 2014
Published in: Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2261250.2261293
Recommendations
- Conflict-Free Colorings of Rectangles Ranges
- Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
- Conflict-free coloring of points on a line with respect to a set of intervals
- Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
- Conflict-free coloring of points and simple regions in the plane
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cited In (14)
- Coloring Delaunay-edges and their generalizations
- Geometric Packing under Nonuniform Constraints
- Conflict-free coloring of string graphs
- Conflict-Free Colorings of Rectangles Ranges
- Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
- On conflict-free coloring of points and simple regions in the plane
- Conflict-free coloring of points on a line with respect to a set of intervals
- Hitting and Piercing Rectangles Induced by a Point Set
- Conflict-free colouring of subsets
- Coloring points with respect to squares
- Colouring a dominating set without conflicts: \(q\)-subset square colouring
- How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
- Geometric stabbing via threshold rounding and factor revealing LPs
- Coloring and maximum independent set of rectangles
This page was built for publication: Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874591)
