### Samenvatting

We introduce the fully-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. A coloring is conflict-free if for each point p contained in some interval, p is contained in an interval whose color is not shared with any other interval containing p. 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 Omega(log n/log log n), and that any strategy using O(1/epsilon) colors needs Omega(epsilon n^epsilon) recolorings; - a coloring strategy that uses O(log n) colors at the cost of O(log n) recolorings, and another strategy that uses O(1/epsilon) colors at the cost of O(n^epsilon/epsilon) 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-2 | Engels |
---|---|

Titel | ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand |

Redacteuren | Takeshi Tokuyama, Yoshio Okamoto |

Plaats van productie | Dagstuhl |

Uitgeverij | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pagina's | 26:1-26:13 |

ISBN van elektronische versie | 9783959770545 |

ISBN van geprinte versie | 978-3-95977-054-5 |

DOI's | |

Status | Gepubliceerd - 1 dec 2017 |

Evenement | 28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand Duur: 9 dec 2017 → 12 dec 2017 Congresnummer: 28 http://aiat.in.th/isaac2017/ |

### Publicatie series

Naam | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 92 |

ISSN van geprinte versie | 1868-8969 |

### Congres

Congres | 28th International Symposium on Algorithms and Computation (ISAAC 2017) |
---|---|

Verkorte titel | ISAAC 2017 |

Land | Thailand |

Stad | Phuket |

Periode | 9/12/17 → 12/12/17 |

Internet adres |

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

## Citeer dit

de Berg, M. T., Leijsen, T., Markovic, A., van Renssen, A. M., Roeloffzen, M. J. M., & Woeginger, G. (2017). Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points. In T. Tokuyama, & Y. Okamoto (editors),

*ISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand*(blz. 26:1-26:13). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 92). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2017.26