Every graph with maximum degree Δ can be colored with (Δ+ 1) colors using a simple
greedy algorithm. Remarkably, recent work has shown that one can find such a coloring …

The distributed coloring problem is at the core of the area of distributed graph algorithms
and it is a problem that has seen tremendous progress over the last few years. Much of the …

In this article, we present a deterministic algorithm to compute an O (k Δ)-vertex coloring in O
(Δ/k)+ log* n rounds, where Δ is the maximum degree of the network graph and k≥ 1 can be …

In this paper we present efficient distributed algorithms for classical symmetry breaking
problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the …

We provide new deterministic algorithms for the edge coloring problem, which is one of the
classic and highly studied distributed local symmetry breaking problems. As our main result …

We give a randomized Δ-coloring algorithm in the LOCAL model that runs in poly log log n
rounds, where n is the number of nodes of the input graph and Δ is its maximum degree …

We study the local complexity landscape of locally checkable labeling (LCL) problems on
constant-degree graphs with a focus on complexities below log* n. Our contribution is …

We show fast deterministic algorithms for fundamental problems on forests in the
challenging low-space regime of the well-known Massive Parallel Computation (MPC) …

We continue the recently started line of work on the distributed node-averaged complexity of
distributed graph algorithms. The node-averaged complexity of a distributed algorithm …

We investigate the distributed complexity of maximal matching and maximal independent set
(MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph H=(VH, EH) …