Zobrazeno 1 - 10
of 128
pro vyhledávání: '"Rotenberg, Eva"'
Fredman proposed in 1976 the following algorithmic problem: Given are a ground set $X$, some partial order $P$ over $X$, and some comparison oracle $O_L$ that specifies a linear order $L$ over $X$ that extends $P$. A query to $O_L$ has as input disti
Externí odkaz:
http://arxiv.org/abs/2407.21591
A classical problem in computational geometry and graph algorithms is: given a dynamic set S of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of S. Previous papers studied the setting where, before the
Externí odkaz:
http://arxiv.org/abs/2406.20065
Autor:
Balliu, Alkida, Brandt, Sebastian, Kuhn, Fabian, Nowicki, Krzysztof, Olivetti, Dennis, Rotenberg, Eva, Suomela, Jukka
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem $\Pi
Externí odkaz:
http://arxiv.org/abs/2405.04519
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
Inspired by the seminal result that a graph and an associated rotation system uniquely determine the topology of a closed manifold, we propose a combinatorial method for reconstruction of surfaces from points. Our method constructs a spanning tree an
Externí odkaz:
http://arxiv.org/abs/2402.01893
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
Autor:
Chekuri, Chandra, Christiansen, Aleksander Bjørn, Holm, Jacob, van der Hoog, Ivor, Quanrud, Kent, 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/2310.18146
Autor:
Bringmann, Karl, Fischer, Nick, van der Hoog, Ivor, Kipouridis, Evangelos, Kociumaka, Tomasz, Rotenberg, Eva
The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, especially for temporal data, and is known to be a robust, outlier-insensi
Externí odkaz:
http://arxiv.org/abs/2310.18128
Autor:
Gæde, Emil Toftegaard, Gørtz, Inge Li, van der Hoog, Ivor, Krogh, Christoffer, Rotenberg, Eva
The convex hull of a data set $P$ is the smallest convex set that contains $P$. In this work, we present a new data structure for convex hull, that allows for efficient dynamic updates. In a dynamic convex hull implementation, the following traits ar
Externí odkaz:
http://arxiv.org/abs/2310.18068
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