Simple view
Full metadata view
Authors
Statistics
Dynamic coloring of unit interval graphs with limited recourse budget
dynamic algorithms
unit interval graphs
coloring
recourse budget
parametrized dynamic algorithms
In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the same color. After each update only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains k-colorable at all times, the updates consist of insertions only, and the final instance consists of n intervals, then we can achieve an amortized recourse budget of
cris.lastimport.wos | 2024-04-10T00:04:42Z | |
dc.abstract.en | In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the same color. After each update only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains k-colorable at all times, the updates consist of insertions only, and the final instance consists of n intervals, then we can achieve an amortized recourse budget of $𝒪({k⁷ log n})$ while maintaining a proper coloring with k colors. This is an exponential improvement over the result in [Bartłomiej Bosek et al., 2020] in terms of both k and n. We complement this result by showing the lower bound of $Ω(n)$ on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As an additional application of our techniques we include a new combinatorial result on coloring unit circular arc graphs. Let L be the maximum number of arcs intersecting in one point for some set of unit circular arcs $𝒜$. We show that if there is a set $𝒜'$ of non-intersecting unit arcs of size $L²-1$ such that $𝒜 ∪ 𝒜'$ does not contain L+1 arcs intersecting in one point, then it is possible to color $𝒜$ with L colors. This complements the work on circular arc coloring [Belkale and Chandran, 2009; Tucker, 1975; Valencia-Pabon, 2003], which specifies sufficient conditions needed to color $𝒜$ with L+1 colors or more. | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | pl |
dc.conference | 30th Annual European Symposium on Algorithms | |
dc.conference.city | Berlin/Potsdam | |
dc.conference.country | Niemcy | |
dc.conference.datefinish | 2022-09-07 | |
dc.conference.datestart | 2022-09-05 | |
dc.conference.shortcut | ESA | |
dc.contributor.author | Bosek, Bartłomiej - 114402 | pl |
dc.contributor.author | Zych-Pawlewicz, Anna | pl |
dc.contributor.editor | Chechik, Shiri | pl |
dc.contributor.editor | Navarro, Gonzalo | pl |
dc.contributor.editor | Rotenberg, Eva | pl |
dc.contributor.editor | Herman, Grzegorz | pl |
dc.date.accessioned | 2023-02-02T15:20:18Z | |
dc.date.available | 2023-02-02T15:20:18Z | |
dc.date.issued | 2022 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.conftype | international | pl |
dc.description.physical | 25:1-25:14 | pl |
dc.description.series | Leibniz International Proceedings in Informatics (LIPIcs) | |
dc.description.seriesnumber | 244 | |
dc.description.version | ostateczna wersja wydawcy | |
dc.identifier.doi | 10.4230/LIPIcs.ESA.2022.25 | pl |
dc.identifier.isbn | 978-3-95977-247-1 | pl |
dc.identifier.seriesissn | 1868-8969 | |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/307123 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
dc.pubinfo | Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik | pl |
dc.rights | Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa | * |
dc.rights.licence | CC-BY | |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/legalcode.pl | * |
dc.share.type | inne | |
dc.subject.en | dynamic algorithms | pl |
dc.subject.en | unit interval graphs | pl |
dc.subject.en | coloring | pl |
dc.subject.en | recourse budget | pl |
dc.subject.en | parametrized dynamic algorithms | pl |
dc.subtype | ConferenceProceedings | pl |
dc.title | Dynamic coloring of unit interval graphs with limited recourse budget | pl |
dc.title.container | 30th Annual European Symposium on Algorithms ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany | pl |
dc.type | BookSection | pl |
dspace.entity.type | Publication |