3 citations · 9 across the 9 of their papers we have counts for
12 papers
Augmenting Plane Straight-Line Graphs to Meet Parity Constraints
Aleksander Bjørn Grodt Christiansen, Linda Kleist, Irene Parada +1
Given a plane geometric graph on vertices, we want to augment it so that given parity constraints of the vertex degrees are met. In other words, given a subset of the v…
Local Density and its Distributed Approximation
Aleksander Bjørn Christiansen, Ivor van der Hoog, Eva Rotenberg
The densest subgraph problem is a classic problem in combinatorial optimisation. Danisch, Chan, and Sozio propose a definition for \emph{local density} that assigns to each vertex…
Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
Tijn de Vos, Aleksander B. G. Christiansen
A tree-packing is a collection of spanning trees of a graph. It has been a useful tool for computing the minimum cut in static, dynamic, and distributed settings. In particular, [T…
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…
Deterministic Dynamic Edge Colouring
Aleksander B. G. Christiansen
Given a dynamic graph with vertices and edges subject to insertion an deletions of edges, we show how to maintain a -edge-colouring of without the…
Adaptive Out-Orientations with Applications
Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm +4
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
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…
Improved Dynamic Colouring of Sparse Graphs
Aleksander B. G. Christiansen, Krzysztof D. Nowicki, Eva Rotenberg
Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are com…
The Power of Multi-Step Vizing Chains
Aleksander B G Christiansen
Recent papers [Ber'2022], [GP'2020], [DHZ'2019] have addressed different variants of the (Δ+ 1)-edge colouring problem by concatenating or gluing together many Vizing chains to for…
Adaptive Out-Orientations with Applications
Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog +2
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
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…