Dynamic coloring of unit interval graphs with limited recourse budget

2022
book section
conference proceedings
cris.lastimport.wos2024-04-10T00:04:42Z
dc.abstract.enIn 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.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.conference30th Annual European Symposium on Algorithmspl
dc.conference.cityBerlin/Potsdam
dc.conference.countryNiemcy
dc.conference.datefinish2022-09-07
dc.conference.datestart2022-09-05
dc.conference.shortcutESA
dc.contributor.authorBosek, Bartłomiej - 114402 pl
dc.contributor.authorZych-Pawlewicz, Annapl
dc.contributor.editorChechik, Shiripl
dc.contributor.editorNavarro, Gonzalopl
dc.contributor.editorRotenberg, Evapl
dc.contributor.editorHerman, Grzegorzpl
dc.date.accessioned2023-02-02T15:20:18Z
dc.date.available2023-02-02T15:20:18Z
dc.date.issued2022pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternationalpl
dc.description.physical25:1-25:14pl
dc.description.seriesLeibniz International Proceedings in Informatics (LIPIcs)
dc.description.seriesnumber244
dc.description.versionostateczna wersja wydawcy
dc.identifier.doi10.4230/LIPIcs.ESA.2022.25pl
dc.identifier.isbn978-3-95977-247-1pl
dc.identifier.seriesissn1868-8969
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/307123
dc.languageengpl
dc.language.containerengpl
dc.pubinfoDagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatikpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeinne
dc.subject.endynamic algorithmspl
dc.subject.enunit interval graphspl
dc.subject.encoloringpl
dc.subject.enrecourse budgetpl
dc.subject.enparametrized dynamic algorithmspl
dc.subtypeConferenceProceedingspl
dc.titleDynamic coloring of unit interval graphs with limited recourse budgetpl
dc.title.container30th Annual European Symposium on Algorithms ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germanypl
dc.typeBookSectionpl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-10T00:04:42Z
dc.abstract.enpl
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.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.conferencepl
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.authorpl
Bosek, Bartłomiej - 114402
dc.contributor.authorpl
Zych-Pawlewicz, Anna
dc.contributor.editorpl
Chechik, Shiri
dc.contributor.editorpl
Navarro, Gonzalo
dc.contributor.editorpl
Rotenberg, Eva
dc.contributor.editorpl
Herman, Grzegorz
dc.date.accessioned
2023-02-02T15:20:18Z
dc.date.available
2023-02-02T15:20:18Z
dc.date.issuedpl
2022
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.conftypepl
international
dc.description.physicalpl
25:1-25:14
dc.description.series
Leibniz International Proceedings in Informatics (LIPIcs)
dc.description.seriesnumber
244
dc.description.version
ostateczna wersja wydawcy
dc.identifier.doipl
10.4230/LIPIcs.ESA.2022.25
dc.identifier.isbnpl
978-3-95977-247-1
dc.identifier.seriesissn
1868-8969
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/307123
dc.languagepl
eng
dc.language.containerpl
eng
dc.pubinfopl
Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik
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.enpl
dynamic algorithms
dc.subject.enpl
unit interval graphs
dc.subject.enpl
coloring
dc.subject.enpl
recourse budget
dc.subject.enpl
parametrized dynamic algorithms
dc.subtypepl
ConferenceProceedings
dc.titlepl
Dynamic coloring of unit interval graphs with limited recourse budget
dc.title.containerpl
30th Annual European Symposium on Algorithms ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany
dc.typepl
BookSection
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
1
Views per month
Downloads
bosek_zych-pawlewicz_dynamic_coloring_of_unit_interval_graphs_2022.pdf
4