Arboricity-Dependent Algorithms for Edge Coloring
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914669469368320 |
|---|---|
| author | Bhattacharya, Sayan Costa, Martín Panski, Nadav Solomon, Shay |
| author_facet | Bhattacharya, Sayan Costa, Martín Panski, Nadav Solomon, Shay |
| contents | The problem of edge coloring has been extensively studied over the years. Recently, this problem has received significant attention in the dynamic setting, where we are given a dynamic graph evolving via a sequence of edge insertions and deletions and our objective is to maintain an edge coloring of the graph.
Currently, it is not known whether it is possible to maintain a $(Δ+ O(Δ^{1 - μ}))$-edge coloring in $\tilde{O}(1)$ update time, for any constant $μ> 0$, where $Δ$ is the maximum degree of the graph. In this paper, we show how to efficiently maintain a $(Δ+ O(α))$-edge coloring in $\tilde O(1)$ amortized update time, where $α$ is the arboricty of the graph. Thus, we answer this question in the affirmative for graphs of sufficiently small arboricity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_08367 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Arboricity-Dependent Algorithms for Edge Coloring Bhattacharya, Sayan Costa, Martín Panski, Nadav Solomon, Shay Data Structures and Algorithms The problem of edge coloring has been extensively studied over the years. Recently, this problem has received significant attention in the dynamic setting, where we are given a dynamic graph evolving via a sequence of edge insertions and deletions and our objective is to maintain an edge coloring of the graph. Currently, it is not known whether it is possible to maintain a $(Δ+ O(Δ^{1 - μ}))$-edge coloring in $\tilde{O}(1)$ update time, for any constant $μ> 0$, where $Δ$ is the maximum degree of the graph. In this paper, we show how to efficiently maintain a $(Δ+ O(α))$-edge coloring in $\tilde O(1)$ amortized update time, where $α$ is the arboricty of the graph. Thus, we answer this question in the affirmative for graphs of sufficiently small arboricity. |
| title | Arboricity-Dependent Algorithms for Edge Coloring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.08367 |