MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Ajwani, Deepak
Elbassioni, Khaled M.
Govindarajan, Sathish
Ray, Saurabh		dblp
dblp
dblp
dblp
Not MPG Author(s):
Ray, Saurabh
Editor(s):
Not MPII Editor(s):
Scheideler, Christian
BibTeX cite key*:
Elbassioni2007a
Title, Booktitle
Title*:
Conflict-Free Coloring for Rectangle Ranges Using $\tildeO(n^.382+\epsilon)$ Colors
Booktitle*:
19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 07)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
San Diego, CA, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
9 June 2007
Event End Date:
11 June 2007
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Proceedings
Volume:
Number:
Month:
June
Pages:
(to-appear)
Year*:
2007
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
Note:
To Appear
(LaTeX) Abstract:
Given a set of points $P\subseteq \RR^2$, a \emph{conflict-free coloring} of $P$ 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\cap 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 $\RR^2$ can be conflict-free colored with $\tO(n^{.382+\epsilon})$ colors
in expected polynomial time, for any arbitrarily small $\eps > 0$.
This improves upon the previously known bound of $O(\sqrt{n\log\log n/\log n}$).
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
popular
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2007a,
AUTHOR = {Ajwani, Deepak and Elbassioni, Khaled M. and Govindarajan, Sathish and Ray, Saurabh},
 TITLE = {Conflict-Free Coloring for Rectangle Ranges Using $\tilde{O}(n^{.382+\epsilon})$ Colors},
 BOOKTITLE = {19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 07)},
 PUBLISHER = {ACM},
 YEAR = {2007},
 PAGES = {(to--appear)},
 SERIES = {Proceedings},
 ADDRESS = {San Diego, CA, USA},
 MONTH = {June},
 NOTE = {To Appear},
}

Entry last modified by Deepak Ajwani, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni		Created
03/01/2007 16:35:35
Revisions
6.
5.
4.
3.
2.		Editor(s)
Deepak Ajwani
Deepak Ajwani
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni		Edit Dates
05/06/2007 02:49:08 PM
05/06/2007 02:48:29 PM
02.05.2007 15:28:53
03/02/2007 06:37:58 PM
03/02/2007 05:32:14 PM