6 citations · 27 across the 32 of their papers we have counts for
4 papers · 1 filter
Fast Distributed Brooks' Theorem
Manuela Fischer, Yannic Maus, Magnús M. Halldórsson
We give a randomized -coloring algorithm in the LOCAL model that runs in rounds, where is the number of nodes of the input graph and is its max…
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…
Exponential Speedup Over Locality in MPC with Optimal Memory
Alkida Balliu, Sebastian Brandt, Manuela Fischer +4
Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example p…
Fast Distributed Vertex Splitting with Applications
Magnús M. Halldórsson, Yannic Maus, Alexandre Nolin
We present -round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into parts such that a node of de…