5 citations · 5 across the 2 of their papers we have counts for
11 papers
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
Alkida Balliu, Fabian Kuhn, Dennis Olivetti
The problem of coloring the edges of an -node graph of maximum degree with colors is one of the key symmetry breaking problems in the area of distributed graph algor…
Truly Tight-in- Bounds for Bipartite Maximal Matching and Variants
Sebastian Brandt, Dennis Olivetti
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic -round and a randomized -ro…
Classification of distributed binary labeling problems
Alkida Balliu, Sebastian Brandt, Yuval Efron +4
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable…
Locality of not-so-weak coloring
Alkida Balliu, Juho Hirvonen, Christoph Lenzen +2
Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally…
How much does randomness help with locally checkable problems?
Alkida Balliu, Sebastian Brandt, Dennis Olivetti +1
Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. V…
The distributed complexity of locally checkable problems on paths is decidable
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +3
Consider a computer network that consists of a path with nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a consta…