26 citations · 100 across the 29 of their papers we have counts for
38 papers
Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity
Malte Baumecker, Rustam Latypov, Yannic Maus +1
Given a graph , a -ruling set is a subset of nodes that is independent, and each node in is at distance at most from some node in . In this pa…
Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
Malte Baumecker, Yannic Maus, Jara Uitto
Given a graph , a -ruling set is a subset that is i) independent, and ii) every node has a node of within distance . In this paper we pre…
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…
Shared Randomness Helps with Local Distributed Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +5
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is loca…
Adaptive Massively Parallel Coloring in Sparse Graphs
Rustam Latypov, Yannic Maus, Shreyas Pai +1
Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model…
Conditionally Optimal Parallel Coloring of Forests
Christoph Grunau, Rustam Latypov, Yannic Maus +2
We show the first conditionally optimal deterministic algorithm for -coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in $O(\log…