TY - GEN
T1 - Conflict-free colorings of shallow discs
AU - Alon, Noga
AU - Smorodinsky, Shakhar
PY - 2006
Y1 - 2006
N2 - We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3 k) colors so that for each point p in the union of all discs there is at least one disc in the collection containing p whose color differs from that of all other members of the collection that contain p. This is motivated by a problem on frequency assignments in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.
AB - We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3 k) colors so that for each point p in the union of all discs there is at least one disc in the collection containing p whose color differs from that of all other members of the collection that contain p. This is motivated by a problem on frequency assignments in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.
KW - Conflict-free coloring
KW - Frequency-assignment
KW - Wireless
UR - http://www.scopus.com/inward/record.url?scp=33748043312&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748043312&partnerID=8YFLogxK
U2 - 10.1145/1137856.1137864
DO - 10.1145/1137856.1137864
M3 - Conference contribution
AN - SCOPUS:33748043312
SN - 1595933409
SN - 9781595933409
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 41
EP - 43
BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PB - Association for Computing Machinery (ACM)
T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06
Y2 - 5 June 2006 through 7 June 2006
ER -