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 $\beta$-ruling set is a subset of nodes $S\subseteq V$ that is independent, and each node in $V$ is at distance at most $\beta$ from some node in $S$. In this pa…