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: Goto entry point

 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
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
Attachment Section

View attachments here: