Manuel Jakob

collaborators

3 papers

cs.DS2026

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors

Maxime Flin, MagnÃºs M. HalldÃ³rsson, Manuel Jakob +1

For any $I^$ , let $k_{I^} $ be the maximum integer $k$ such that $(k + 1) (k + 2) \leq I^$ . We give a distributed \LOCAL algorithm that, given an integer $k < k_{I^} $ , computes a valid $I^ - k$ -…

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.DC2025

Towards Optimal Distributed Delta Coloring

Manuel Jakob, Yannic Maus

The $I^$ -vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The maj…