6 citations · 27 across the 32 of their papers we have counts for
6 papers · 1 filter
Distributed Sparsest Cut via Eigenvalue Estimation
Yannic Maus, Tijn de Vos
We give new, improved bounds for approximating the sparsest cut value or in other words the conductance of a graph in the CONGEST model. As our main result, we present an algor…
Towards Optimal Distributed Edge Coloring with Fewer Colors
Manuel Jakob, Yannic Maus, Florian Schager
There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime exam…
On Distributed Colouring of Hyperbolic Random Graphs
Yannic Maus, Janosch Ruff
We analyse the performance of simple distributed colouring algorithms under the assumption that the input graph is a hyperbolic random graph (HRG), a generative model capturing key…
Towards Optimal Distributed Delta Coloring
Manuel Jakob, Yannic Maus
The -vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The majo…
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…