Yannic Maus

activity

20152026

most citedImproved Distributed Degree Splitting and Edge Coloring

6 citations · 27 across the 32 of their papers we have counts for

collaborators

Showing 2020Show all

5 papers · 1 filter

cs.DS2020

Efficient Randomized Distributed Coloring in CONGEST

Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus +1

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomiz…

cs.DC2020

Coloring Fast Without Learning Your Neighbors' Colors

Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus +1

We give an improved randomized CONGEST algorithm for distance- $2$ coloring that uses $Δ^{2} + 1$ colors and runs in $O (lo g n)$ rounds, improving the recent $O (lo g Δ \cdot lo g n)$ -rou…

cs.DS2020

Local Conflict Coloring Revisited: Linial for Lists

Yannic Maus, Tigran Tonoyan

Linial's famous color reduction algorithm reduces a given $m$ -coloring of a graph with maximum degree $Δ$ to a $O (Δ^{2} lo g m)$ -coloring, in a single round in the LOCAL model. We sho…

cs.DS2020

Distributed Approximation on Power Graphs

Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus +2

We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^{2}$ . While we focus mostly on exploring this theme in t…

cs.DC2020

Distance-2 Coloring in the CONGEST Model

Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus

We give efficient randomized and deterministic distributed algorithms for computing a distance- $2$ vertex coloring of a graph $G$ in the CONGEST model. In particular, if $Δ$ is the…