8 papers · 1 filter
Adaptive Massively Parallel Coloring in Sparse Graphs
Rustam Latypov, Yannic Maus, Shreyas Pai +1
Classic symmetry-breaking problems on graphs have gained a lot of attention in models of modern parallel computation. The Adaptive Massively Parallel Computation (AMPC) is a model…
Conditionally Optimal Parallel Coloring of Forests
Christoph Grunau, Rustam Latypov, Yannic Maus +2
We show the first conditionally optimal deterministic algorithm for -coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in $O(\log…
Fast Dynamic Programming in Trees in the MPC Model
Chetan Gupta, Rustam Latypov, Yannic Maus +6
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in rounds in the massively parallel computation model (MPC), with…
Adaptive Massively Parallel Connectivity in Optimal Space
Rustam Latypov, Jakub Łącki, Yannic Maus +1
We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the s…
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…
Towards a Complexity Classification of LCL Problems in Massively Parallel Computation
Sebastian Brandt, Rustam Latypov, Jara Uitto
In this work, we develop the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We present a general method th…
Coloring Trees in Massively Parallel Computation
Rustam Latypov, Jara Uitto
We present time 3-coloring, maximal independent set and maximal matching algorithms for trees in the Massively Parallel Computation (MPC) model. Our algorithms a…