Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


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



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

URL of the conference:


URL for downloading the paper:

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 PQ 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
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
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section