Strong fault-tolerant conflict-free coloring (Strong FTCF Coloring) for intervals
Vinay Kumar Singhal, Akanksha Rastogi · International Journal of Research Studies in Computing · 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. Also base stations in cellular networks are often not reliable. Some base station may fail to function properly or get faulted. This leads us to study fault-tolerant CF-colorings: colorings that remain conflict-free even after some objects are deleted from P. We provide a strong fault-tolerant conflict-free coloring (Strong-FTCF coloring) framework for intervals of points such that if some colors gets faulted, the whole system will remain working. We can say that the system is working properly if some of the colors are deleted. Our algorithm uses O(log n) colors with high probability.