1 citations · 1 across the 5 of their papers we have counts for
11 papers · 1 filter
Optimal Deterministic Massively Parallel Connectivity on Forests
Alkida Balliu, Rustam Latypov, Yannic Maus +2
We show fast deterministic algorithms for fundamental problems on forests in the challenging low-space regime of the well-known Massive Parallel Computation (MPC) model. A recent b…
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bou…
Local Mending
Alkida Balliu, Juho Hirvonen, Darya Melnyk +3
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far o…
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…