Unpublished, Draft, To Appear
@UnPublished
Unveröffentlicht, Entwurf


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









Author, Editor

Author(s):

Elbassioni, Khaled M.
Mustafa, Nabil H.

dblp
dblp



BibTeX citekey*:

Elbassioni2005a

Title, Booktitle

Title*:

Conflict-Free Colorings of Rectangle Ranges for Wireless Networks

Vol, No, pp., Year

Month:

January

Year:

2005

Language:

English

Pages:


Abstract, Links, ©

Note:


LaTeX Abstract:

In this paper we study the problem of frequency assignment in wireless cellular networks under the framework of \emph{conflict-free colorings}. Given the range space $(P, \mathcal{R})$, where $P$ is a small set of $n$ points
in $\Re^2$, one would like to color $P$ with the minimum number of colors such that $(P, \cR)$ is conflict-free. This problem has been studied in a series of recent works~\cite{ELRS02,HS03,FLMMPSSWW05}.
We continue this study with the following question: Given $P$, is it possible to add a few set of points $Q$ such that
$( P \cup Q, \cR)$ can be colored with fewer colors than $(P, \cR)$? When the range spaces are intervals in $\Re$ or discs in $\Re^2$, a negative answer follows from previous work~\cite{PT03}. Surprisingly, we answer this question
in the affirmative for the case of rectangle ranges. Our main result is that, given $P$, and any $\eps \geq 0$,
one can always add a set $Q$ of $O(n^{1-\eps})$ points such that $P \cup Q$ can be conflict-free colored using $\tilde O( n^{\frac{3}{8} (1+\eps)} )$ colors.
Moreover, the set $Q$ and the conflict-free coloring can be computed in polynomial time. Our result is obtained by introducing a general probabilistic re-coloring technique,
which we call \emph{quasi-conflict-free} coloring, and which may be of independent interest. A further application of this technique is also given.

Categories / Keywords:


HyperLinks / References / URLs:


Personal Comments:


File Upload:




Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@UNPUBLISHED{Elbassioni2005a,
AUTHOR = {Elbassioni, Khaled M. and Mustafa, Nabil H.},
TITLE = {Conflict-Free Colorings of Rectangle Ranges for Wireless Networks},
YEAR = {2005},
MONTH = {January},
}


Entry last modified by Christine Kiesel, 05/02/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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/16/2005 04:03:37 PM
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Christine Kiesel
Khaled Elbassioni

Edit Dates
02.05.2007 15:38:31
19.06.2006 09:55:56
03/16/2005 04:03:38 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
rectangles.ps