Recoloring interval graphs with limited recourse budget

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Recoloring interval graphs with limited recourse budget

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GJ17-10090Y" target="_blank" >GJ17-10090Y: Network Optimization</a><br>

Continuities

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

Publication year

2020

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

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

ISBN

978-3-95977-150-4

ISSN

1868-8969

e-ISSN

—

Number of pages

23

Pages from-to

1-23

Publisher name

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Torshavn, Faroe Islands

Event date

Jun 22, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—