Conflict-free coloring for rectangle ranges using O(n.382) colors

Files in This Item:
File Description SizeFormat 
ajwani_spaa07.pdf131.88 kBAdobe PDFDownload
Title: Conflict-free coloring for rectangle ranges using O(n.382) colors
Authors: Ajwani, Deepak
Elbassioni, Khaled
Govindarajan, Sathish
Ray, Saurabh
Permanent link:
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 networksConflict-free coloringAxis-parallel rectanglesDominating setsMonotone sequences
DOI: 10.1145/1248377.1248406
Other versions:
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

Citations 10

Last Week
Last month
checked on May 19, 2019

Google ScholarTM



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.