Conflict-free coloring with respect to a subset of intervals

2013 IJRSC – Volume 2 Issue 2

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 H_n 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 H_n. i.e. any subset of possible intervals. If in this hypergraph, the hyperedge have 1_n number of vertices then we show that the algorithm uses at most ⌊1_n/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

PDF

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