Malte Baumecker

collaborators

3 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

Distributed Santa Claus via Global Rounding

Tijn de Vos, Leo Wennmann, Malte Baumecker +2

In this paper, we consider the Santa Claus problem in the CONGEST model. This NP-hard problem can be modeled as a bipartite graph of children and gifts where an edge indicates that…

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…