Sparsity-Parameterised Dynamic Edge Colouring
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_ | 1866916565979496448 |
|---|---|
| author | Christiansen, Aleksander B. G. Rotenberg, Eva Vlieghe, Juliette |
| author_facet | Christiansen, Aleksander B. G. Rotenberg, Eva Vlieghe, Juliette |
| contents | We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph's arboricity, $α$. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updates a proper $Δ+ O(α)$ edge~colouring in $\operatorname{poly}(\log n)$ amortized time. Our algorithm is fully adaptive to the current value of the maximum degree and arboricity.
In this fully-dynamic setting, the state-of-the-art edge-colouring algorithms are either a randomised algorithm using $(1 + \varepsilon)Δ$ colours in $\operatorname{poly}(\log n, ε^{-1})$ time per update, or the naive greedy algorithm which is a deterministic $2Δ-1$ edge colouring with $\log(Δ)$ update time.
Compared to the $(1+\varepsilon)Δ$ algorithm, our algorithm is deterministic and asymptotically faster, and when $α$ is sufficiently small compared to $Δ$, it even uses fewer colours. In particular, ours is the first $Δ+O(1)$ edge-colouring algorithm for dynamic forests, and dynamic planar graphs, with polylogarithmic update time.
Additionally, in the static setting, we show that we can find a proper edge colouring with $Δ+ 2α$ colours in $O(m\log n)$ time. Moreover, the colouring returned by our algorithm has the following local property: every edge $uv$ is coloured with a colour in $\{1, \max\{deg(u), deg(v)\} + 2α\}$. The time bound matches that of the greedy algorithm that computes a $2Δ-1$ colouring of the graph's edges, and improves the number of colours when $α$ is sufficiently small compared to $Δ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_10616 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sparsity-Parameterised Dynamic Edge Colouring Christiansen, Aleksander B. G. Rotenberg, Eva Vlieghe, Juliette Data Structures and Algorithms We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph's arboricity, $α$. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updates a proper $Δ+ O(α)$ edge~colouring in $\operatorname{poly}(\log n)$ amortized time. Our algorithm is fully adaptive to the current value of the maximum degree and arboricity. In this fully-dynamic setting, the state-of-the-art edge-colouring algorithms are either a randomised algorithm using $(1 + \varepsilon)Δ$ colours in $\operatorname{poly}(\log n, ε^{-1})$ time per update, or the naive greedy algorithm which is a deterministic $2Δ-1$ edge colouring with $\log(Δ)$ update time. Compared to the $(1+\varepsilon)Δ$ algorithm, our algorithm is deterministic and asymptotically faster, and when $α$ is sufficiently small compared to $Δ$, it even uses fewer colours. In particular, ours is the first $Δ+O(1)$ edge-colouring algorithm for dynamic forests, and dynamic planar graphs, with polylogarithmic update time. Additionally, in the static setting, we show that we can find a proper edge colouring with $Δ+ 2α$ colours in $O(m\log n)$ time. Moreover, the colouring returned by our algorithm has the following local property: every edge $uv$ is coloured with a colour in $\{1, \max\{deg(u), deg(v)\} + 2α\}$. The time bound matches that of the greedy algorithm that computes a $2Δ-1$ colouring of the graph's edges, and improves the number of colours when $α$ is sufficiently small compared to $Δ$. |
| title | Sparsity-Parameterised Dynamic Edge Colouring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.10616 |