Options
Conflict-free coloring for rectangle ranges using O(n.382) colors
Date Issued
2007-06-11
Date Available
2019-04-11T08:49:26Z
Abstract
Given a set of points P ⊆ R 2 , a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each non-empty axis-parallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T. This notion has been the subject of recent interest, and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to bases stations (points), such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R 2 can be conflict-free colored with O˜(n β+ ) colors in expected polynomial time, for any arbitrarily small > 0 and β = 3− √ 5 2 < 0.382. This improves upon the previously known bound of O( p n log log n/ log n).
Type of Material
Conference Publication
Publisher
ACM
Copyright (Published Version)
2007 ACM
Web versions
Language
English
Status of Item
Peer reviewed
Part of
SPAA '07 Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures
Conference Details
The 19th ACM Symposium on Parallelism in Algorithms and Architectures, San Diego, California, 9-11 June 2007
ISBN
159593667X
9781595936677
This item is made available under a Creative Commons License
File(s)
Owning collection
Scopus© citations
26
Acquisition Date
Mar 28, 2024
Mar 28, 2024
Views
704
Acquisition Date
Mar 28, 2024
Mar 28, 2024
Downloads
353
Last Week
3
3
Last Month
11
11
Acquisition Date
Mar 28, 2024
Mar 28, 2024