Conflict-free coloring for rectangle ranges using O(n.382) colors
|Title:||Conflict-free coloring for rectangle ranges using O(n.382) colors||Authors:||Ajwani, Deepak
|Permanent link:||http://hdl.handle.net/10197/9905||Date:||11-Jun-2007||Online since:||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||Keywords:||Frequency assignment in wireless networks; Conflict-free coloring; Axis-parallel rectangles; Dominating sets; Monotone sequences||DOI:||10.1145/1248377.1248406||Other versions:||http://www.cs.jhu.edu/~spaa/2007/||Language:||en||Status of Item:||Peer reviewed||Is 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
|Appears in Collections:||Computer Science Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.