Zobrazeno 1 - 10
of 16
pro vyhledávání: '"Christiansen, Aleksander B. G."'
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, [Thorup, Comb. 2007] used them to obtain his dynamic min-cut algorithm w
Externí odkaz:
http://arxiv.org/abs/2405.09141
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 fundamental questions about a graph. In this paper, we study the vertex
Externí odkaz:
http://arxiv.org/abs/2404.18692
Given a dynamic graph $G$ with $n$ vertices and $m$ edges subject to insertion an deletions of edges, we show how to maintain a $(1+\varepsilon)\Delta$-edge-colouring of $G$ without the use of randomisation. More specifically, we show a deterministic
Externí odkaz:
http://arxiv.org/abs/2402.13139
We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph's arboricity, $\alpha$. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updat
Externí odkaz:
http://arxiv.org/abs/2311.10616
We show that every planar triangulation on $n>10$ vertices has a dominating set of size $n/7=n/3.5$. This approaches the $n/4$ bound conjectured by Matheson and Tarjan [MT'96], and improves significantly on the previous best bound of $17n/53\approx n
Externí odkaz:
http://arxiv.org/abs/2310.11254
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 computable upon query time. We give a deterministic algorithm that uses $
Externí odkaz:
http://arxiv.org/abs/2211.06858
Autor:
Christiansen, Aleksander B G
Recent papers [Ber'2022], [GP'2020], [DHZ'2019] have addressed different variants of the (\Delta + 1)-edge colouring problem by concatenating or gluing together many Vizing chains to form what Bernshteyn [Ber'2022] coined \emph{multi-step Vizing chai
Externí odkaz:
http://arxiv.org/abs/2210.07363
Autor:
Christiansen, Aleksander B. G., Holm, Jacob, van der Hoog, Ivor, Rotenberg, Eva, Schwiegelshohn, Chris
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 edges such that the out-degree of each vertex is proportional to the ar
Externí odkaz:
http://arxiv.org/abs/2209.14087
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 facilitating interspersed queries to the colours of vertices. The goal
Externí odkaz:
http://arxiv.org/abs/2203.06039
Publikováno v:
Christiansen, A B G & Rotenberg, E 2022, Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring . in M Bojanczyk, E Merelli & D P Woodruff (eds), Proceedings of 49 th EATCS International Conference on Automata, Languages, and Programming ., 42, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 229, 49 th EATCS International Conference on Automata, Languages, and Programming, Paris, France, 04/07/2022 . https://doi.org/10.4230/LIPIcs.ICALP.2022.42
The arboricity α of a graph is the smallest number of forests necessary to cover its edges, and an arboricity decomposition of a graph is a decomposition of its edges into forests. The best near-linear time algorithm for arboricity decomposition gua
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b2b0c50958585210eeb083cd3a8e6ec0
https://orbit.dtu.dk/en/publications/c75421b9-95a5-4796-9082-0c4d2093f48b
https://orbit.dtu.dk/en/publications/c75421b9-95a5-4796-9082-0c4d2093f48b