Randomized Algorithm for Conflict-Free Coloring of Graphs & Hypergraphs
Vinay Kumar Singhal, Akanksha Rastogi · 2012
Given a set of points P, a conflict-free coloring of P is an assignment of colors to points of P, such that there exist a point p in any subset of P whose color is distinct from all other points in that subset of P. This notion is motivated by frequency assignment in wireless cellular networks: one would like to minimize the number of frequencies (colors) assigned to base stations (points), such that within any range, there is no interference. We provide a framework for randomized conflict-free coloring (CF-coloring) any k-degenerate hypergraph. Our algorithm uses O(log n) colors with high probability.