2 papers
cs.DS2024
Private graph colouring with limited defectiveness
Aleksander B. G. Christiansen, Eva Rotenberg, Teresa Anna Steiner +1
Differential privacy is the gold standard in the problem of privacy preserving data analysis, which is crucial in a wide range of disciplines. Vertex colouring is one of the most f…
cs.DS2023
Sparsity-Parameterised Dynamic Edge Colouring
Aleksander B. G. Christiansen, Eva Rotenberg, Juliette Vlieghe
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 inser…