Fault-tolerant conflict-free coloring

M.A. Abam, M.T. Berg, de, S.H. Poon

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)
2 Downloads (Pure)


Background. Consider a cellular network consisting of a set of base stations, where the signal from a given base station can be received by clients within a certain distance from the base station. In general, these regions will overlap. For a client, this may lead to interference of the signals. Thus one would like to assign frequencies to the base stations such that for any client within reach of at least one base station, there is a base station within reach with a unique frequency (among all the ones within reach). The goal is to do this using only few distinct frequencies. Recently, Even et al. [5] intro- duced conict-free colorings, as de??ned next, to model this problem. Let S be a set of n objects, and let R be a, possibly in??nite, family of ranges. In this paper, we only consider objects and ranges that are subsets of R2, or sometimes of R1. For a range r 2 R, let S(r) be the subset of objects from S intersecting the range r. A conict-free coloring (CF-coloring) of S with respect to R is a coloring of S with the following property [5]: for any range r 2 R for which S(r) 6= ; there is an object o 2 S(r) with a unique color in S(r), that is, with a color not used by any other object in S(r). Trivially, a conict-free coloring always exists: just assign a di??erent color to each object. However, one would like to ??nd a coloring with only few colors. This is the conict-free coloring problem. Note that if we take S to be a set of disks|namely, the regions within reach of each base station|and we take R to be the set of all points in R2, then we get exactly the range-assignment problem discussed earlier. However, other versions|for example the dual version, where S is a point set and R is the family of all disks|are interesting as well.
Original languageEnglish
Title of host publicationProceedings 20th Canadian Conference on Computational Geometry (CCCG'08, Montréal, Québec, Canada, August 13-15, 2008)
PublisherCCCG Library
Publication statusPublished - 2008


Dive into the research topics of 'Fault-tolerant conflict-free coloring'. Together they form a unique fingerprint.

Cite this