11 papers
Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity
Malte Baumecker, Rustam Latypov, Yannic Maus +1
Given a graph , a -ruling set is a subset of nodes that is independent, and each node in is at distance at most from some node in . In this pa…
Near-Optimal Directed Low-Diameter Decompositions
Karl Bringmann, Nick Fischer, Bernhard Haeupler +1
Low Diameter Decompositions (LDDs) are invaluable tools in the design of combinatorial graph algorithms. While historically they have been applied mainly to undirected graphs, in t…
A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
Nick Fischer, Bernhard Haeupler, Rustam Latypov +2
We give the first parallel algorithm with optimal work for the classical problem of computing Single-Source Shortest Paths in general graphs with negative-weight edg…
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…