17 citations · 17 across the 4 of their papers we have counts for
5 papers
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…
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…
Distributed Symmetry Breaking on Power Graphs via Sparsification
Yannic Maus, Saku Peltonen, Jara Uitto
In this paper, we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the…
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…
Local algorithms in (weakly) coloured graphs
Matti Åstrand, Valentin Polishchuk, Joel Rybicki +2
A local algorithm is a distributed algorithm that completes after a constant number of synchronous communication rounds. We present local approximation algorithms for the minimum d…