7 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…
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…
Hardness of minimal symmetry breaking in distributed computing
Alkida Balliu, Juho Hirvonen, Dennis Olivetti +1
A graph is weakly -colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we…