
Distributed Graph Coloring Made Easy
In this paper we present a deterministic CONGEST algorithm to compute an...
read it

Locally Checkable Labelings with Small Messages
A rich line of work has been addressing the computational complexity of ...
read it

NearOptimal Scheduling in the Congested Clique
This paper provides three nearlyoptimal algorithms for scheduling t job...
read it

Efficient Randomized Distributed Coloring in CONGEST
Distributed vertex coloring is one of the classic problems and probably ...
read it

Coloring Fast Without Learning Your Neighbors' Colors
We give an improved randomized CONGEST algorithm for distance2 coloring...
read it

Local Conflict Coloring Revisited: Linial for Lists
Linial's famous color reduction algorithm reduces a given mcoloring of ...
read it

Distributed Approximation on Power Graphs
We investigate graph problems in the following setting: we are given a g...
read it

Distance2 Coloring in the CONGEST Model
We give efficient randomized and deterministic distributed algorithms fo...
read it

Efficient Deterministic Distributed Coloring with Small Bandwidth
We show that the (degree+1)list coloring problem can be solved determin...
read it

Classification of distributed binary labeling problems
We present a complete classification of the deterministic distributed ti...
read it

A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovasz Local Lemma
The Lovász Local Lemma (LLL) says that, given a set of bad events that d...
read it

PSLOCALCompleteness of Maximum Independent Set Approximation
We prove that the maximum independent set approximation problem with pol...
read it

On the Complexity of Distributed Splitting Problems
One of the fundamental open problems in the area of distributed graph al...
read it

Deterministic Distributed Dominating Set Approximation in the CONGEST Model
We develop deterministic approximation algorithms for the minimum domina...
read it

Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol
We study a process of averaging in a distributed system with noisy commu...
read it

Deterministic Distributed Ruling Sets of Line Graphs
An (α,β)ruling set of a graph G=(V,E) is a set R⊆ V such that for any n...
read it

Improved Distributed ΔColoring
We present a randomized distributed algorithm that computes a Δcoloring...
read it

Local Distributed Algorithms in Highly Dynamic Networks
The present paper studies local distributed graph problems in highly dyn...
read it

Deterministic Distributed EdgeColoring with Fewer Colors
We present a deterministic distributed algorithm, in the LOCAL model, th...
read it
Yannic Maus
is this you? claim profile