Available Online: 24 June 2012
Author/s:
Singhal, Vinay Kumar*
Department of MCA, Meerut Institute of Engineering & Technology, Meerut, Uttar Pradesh, India (singhalmca04@gmail.com)
Rastogi, Akanksha
Department of MCA, Meerut Institute of Engineering & Technology, Meerut, Uttar Pradesh, India (akanksharastogi.mca@gmail.com)
Abstract:
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.
Keywords: frequency-assignment problem; cellular network; intervals; conflict-free coloring; strong fault-tolerant
DOI: https://doi.org/10.5861/ijrsc.2012.137
Cite this article:
Singhal, V. K., & Rastogi, A. (2012). Strong fault-tolerant conflict-free coloring (Strong FTCF Coloring) for intervals. International Journal of Research Studies in Computing, 1(2), 21-26. https://doi.org/10.5861/ijrsc.2012.137
*Corresponding Author