Dynamic and kinetic conflict-free coloring of intervals with respect to points

M.T. de Berg, T. Leijsen, André M. van Renssen, M.J.M. Roeloffzen, A. Markovic, G. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

34 Downloads (Pure)

Samenvatting

We introduce the dynamic conflict-free coloring problem for a set S of intervals in R 1 with respect to points, where the goal is to maintain a conflict-free coloring for S under insertions and deletions. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include:
- a lower bound on the number of recolorings as a function of the number of colors, which implies that with O(1) recolorings per update the worst-case number of colors is Ω(logn/loglogn) , and that any strategy using O(1/ε) colors needs Ω(εn ε ) recolorings;
- a coloring strategy that uses O(logn) colors at the cost of O(logn) recolorings, and another strategy that uses O(1/ε) colors at the cost of O(n ε /ε) recolorings;
- stronger upper and lower bounds for special cases.
We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight.
Originele taal-2Engels
Artikelnummer1701.03388
Aantal pagina's17
TijdschriftarXiv
Nummer van het tijdschrift1701.03388
StatusGepubliceerd - 2017

Vingerafdruk Duik in de onderzoeksthema's van 'Dynamic and kinetic conflict-free coloring of intervals with respect to points'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit