Conflict-free coloring of points on a line with respect to a set of intervals

DOI10.1016/j.comgeo.2012.01.013zbMath1248.05067OpenAlexW1971209363MaRDI QIDQ452451

Gila Morgenstern, Matthew J. Katz, Nissan Lev-Tov

Publication date: 21 September 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.01.013

zbMATH Keywords

approximation algorithmsfrequency assignmentconflict-free coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (5)

On Conflict-Free Multi-coloring ⋮ Polynomial Time Algorithms for Bichromatic Problems ⋮ Complexity of conflict-free colorings of graphs ⋮ Strong conflict-free coloring for intervals ⋮ Convex partial transversals of planar regions

Cites Work

• Unnamed Item
• Unit disk graphs
• Conflict-free coloring of points and simple regions in the plane
• CONFLICT-FREE COLORINGS OF SHALLOW DISCS
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Deterministic conflict-free coloring for intervals
• Online Conflict‐Free Coloring for Intervals

This page was built for publication: Conflict-free coloring of points on a line with respect to a set of intervals