MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Elbassioni, Khaled M.
Mustafa, Nabil H.		dblp
dblp
Editor(s):
Durand, Bruno
Thomas, Wolfgang		dblp
dblp
Not MPII Editor(s):
Durand, Bruno
Thomas, Wolfgang
BibTeX cite key*:
Elbassioni2006b
Title, Booktitle
Title*:
Conflict-Free Colorings of Rectangle Ranges
Booktitle*:
STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/y0j8710237486238/fulltext.pdf
Event Address*:
Marseille, France
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
23 February 2006
Event End Date:
25 February 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3884
Number:
Month:
February
Pages:
254-263
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:

Given the range space , where P is a set of n points in and is the family of subsets of P induced by all axis-parallel rectangles, the conflict-free coloring problem asks for a coloring of P with the minimum number of colors such that is conflict-free. We study the following question: Given P, is it possible to add a small set of points Q such that can be colored with fewer colors than ? Our main result is the following: given P, and any , one can always add a set Q of points such that P ∪ Q can be conflict-free colored using 1 colors. Moreover, the set Q and the conflict-free coloring can be computed in polynomial time, with high probability. Our result is obtained by introducing a general probabilistic re-coloring technique, which we call quasi-conflict-free coloring, and which may be of independent interest. A further application of this technique is also given.
URL for the Abstract:
http://www.springerlink.com/content/y0j8710237486238/
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:

@INPROCEEDINGS{Elbassioni2006b,
AUTHOR = {Elbassioni, Khaled M. and Mustafa, Nabil H.},
 EDITOR = {Durand, Bruno and Thomas, Wolfgang},
 TITLE = {Conflict-Free Colorings of Rectangle Ranges},
 BOOKTITLE = {STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {3884},
 PAGES = {254--263},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Marseille, France},
 MONTH = {February},
}

Entry last modified by Christine Kiesel, 05/02/2007
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
04/05/2006 02:37:48 AM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni		Edit Dates
02.05.2007 15:29:52
07.02.2007 15:36:53
07.02.2007 15:36:36
04/05/2006 03:03:15 PM
04/05/2006 02:37:48 AM