2026-07-21T12:47:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20060 2024-05-31T13:11:11Z ddc:004 open_access

Sparsity-Parameterised Dynamic Edge Colouring Christiansen, Aleksander B. G. Rotenberg, Eva Vlieghe, Juliette edge colouring arboricity hierarchical partition dynamic algorithms amortized analysis 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 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 + ε)Δ colours in 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+ε)Δ 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(mlog 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 Δ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksander B. G. Christiansen and Eva Rotenberg and Juliette Vlieghe 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.20 urn:nbn:de:0030-drops-200608 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.20 eng https://creativecommons.org/licenses/by/4.0/legalcode