3 papers
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.DS2025
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…
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…