Recoloring interval graphs with limited recourse budget

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420376" target="_blank" >RIV/00216208:11320/20:10420376 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.SWAT.2020.17" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.SWAT.2020.17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.SWAT.2020.17" target="_blank" >10.4230/LIPIcs.SWAT.2020.17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Recoloring interval graphs with limited recourse budget

Popis výsledku v původním jazyce

We consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors.

Název v anglickém jazyce

Recoloring interval graphs with limited recourse budget

Popis výsledku anglicky

We consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GJ17-10090Y" target="_blank" >GJ17-10090Y: Optimalizace sítí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

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

Název statě ve sborníku

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

ISBN

978-3-95977-150-4

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

23

Strana od-do

1-23

Název nakladatele

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Místo vydání

Dagstuhl

Místo konání akce

Torshavn, Faroe Islands

Datum konání akce

22. 6. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—