J. Uitto

collaborators

4 papers

cs.DS2026

Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity

Malte Baumecker, Rustam Latypov, Yannic Maus +1

Given a graph $G = (V, E)$ , a $I^^{2}$ -ruling set is a subset of nodes $S \subseteq V$ that is independent, and each node in $V$ is at distance at most $I^^{2}$ from some node in $S$ . In this…

cs.DS2026

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs

Malte Baumecker, Yannic Maus, Jara Uitto

Given a graph $G = (V, E)$ , a $I^^{2}$ -ruling set is a subset $S \subseteq V$ that is i) independent, and ii) every node $v \in V$ has a node of $S$ within distance $I^^{2}$ . In this paper we p…

cs.DS2025

A $(3 + ε)$ -Approximate Correlation Clustering Algorithm in Dynamic Streams

Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming algorithms for correlation clustering, where…

cs.DS2025

On the Locality of Hall's Theorem

Sebastian Brandt, Yannic Maus, Ananth Narayanan +2

The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lowe…

Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs

A (3+ε)-Approximate Correlation Clustering Algorithm in Dynamic Streams

On the Locality of Hall's Theorem

A $(3 + ε)$ -Approximate Correlation Clustering Algorithm in Dynamic Streams