Zobrazeno 1 - 10
of 980
pro vyhledávání: '"Christiansen, A. B."'
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
Autor:
Pedersen, Natascha H., Grøntved, Anders, Møller, Niels C., Debrabant, Birgit, Larsen, Kristian T., Brønd, Jan C., Troelsen, Jens, Brage, Søren, Hjelmborg, Jacob v B., Wedderkopp, Niels, Christiansen, Lars B., Mortensen, Sofie R., Egebæk, Heidi K., Toftager, Mette, Heidemann, Malene S., Kristensen, Peter L.
Publikováno v:
In Public Health in Practice June 2024 7
