18 citations · 27 across the 26 of their papers we have counts for
4 papers · 1 filter
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…
Lower bounds for maximal matchings and maximal independent sets
Alkida Balliu, Sebastian Brandt, Juho Hirvonen +3
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in communication rounds; here is the number of nodes and …