Available Online: 29 October 2013
Author/s:
Singhal, Vinay*
Meerut Institute of Engineering & Technology, Meerut, India (singhalmca04@gmail.com)
Rastogi, Akanksha
Meerut Institute of Engineering & Technology, Meerut, India (akanksharastogi.mca@gmail.com)
Abstract:
Given a hypergraph H = (V, E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex in S whose color is distinct from the colors of all other vertices in S. The discrete interval hypergraph Hn is the hypergraph with vertex set {1, . . . , n} and hyperedge set the family of all subsets of consecutive integers in {1, . . . , n}. We provide an algorithm for conflict-free coloring any subhypergraph of Hn. i.e. any subset of possible intervals. If in this hypergraph, the hyperedge have 1n number of vertices then we show that the algorithm uses at most ⌊1n/2⌋ colors and we prove that our analysis is tight.
Keywords: frequency-assignment problem; cellular network; conflict-free coloring; intervals; subset of intervals; fully-covered algorithm
DOI: https://doi.org/10.5861/ijrsc.2013.547
Cite this article:
Singhal, V., & Rastogi, A. (2013). Conflict-free coloring with respect to a subset of intervals. International Journal of Research Studies in Computing, 2(2), 13-24. https://doi.org/10.5861/ijrsc.2013.547
*Corresponding Author