On-line conflict-free colorings for intervals

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F05%3A00000723" target="_blank" >RIV/00216208:11320/05:00000723 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On-line conflict-free colorings for intervals
Original language description
We suppose that n points on the real line are inserted one by one, and each inserted points should be assigned one of k colors, so that at any moment the coloring of the already inserted points is conflict-free, that is, each interval with at least one point contains a point whose colors occurs exactly once in that interval. We investigate algorithms for such coloring, aiming at k as small as possible.
Czech name
On-line bezkonfliktní obarvení intervalů
Czech description
Předpokládejme, že n bodů je po jednom umisťováno na reálnou přímku a každému vloženému bodu je přiřazena jedna z k barev tak, že v každém okamžiku je obarvení vložených bodů bezkonfliktní, což znamená, že každý interval s alespoň jedním bodem obsahuje bod, jehož barva se v tomto intervalu vyskytuje právě jednou. Zkoumáme algoritmy pro takovéto obarvení, s cílem dosáhnout co nejmenší hodnoty k.

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms
ISBN
0-89871-585-7
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
545-554
Publisher name
Society for Industrial and Applied Mathematics
Place of publication
Philadelphia, PA, USA
Event location
Philadelphia, PA, USA
Event date
Jan 1, 2005
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)