1 citations · 1 across the 4 of their papers we have counts for
5 papers
The Gallai Vertex Problem is -Complete
Amir Nikabadi, Eva Rotenberg, Lasse Wulf
When a graph admits a vertex that is contained in all its longest paths, we call a Gallai vertex. These are named after Gallai, who in 1966 asked the question if it is…
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…
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…
Triangulations Admit Dominating Sets of Size
Aleksander B. G. Christiansen, Eva Rotenberg, Daniel Rutschmann
We show that every planar triangulation on vertices has a dominating set of size . This approaches the bound conjectured by Matheson and Tarjan [MT'96], and…
Fully-dynamic Arboricity Decomposition and Implicit Colouring
Aleksander B. G. Christiansen, Eva Rotenberg
In the implicit dynamic colouring problem, the task is to maintain a representation of a proper colouring as a dynamic graph is subject to insertions and deletions of edges, while…