3 citations · 5 across the 12 of their papers we have counts for
4 papers · 1 filter
The Message Complexity of Distributed Graph Optimization
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan +2
The message complexity of a distributed algorithm is the total number of messages sent by all nodes over the course of the algorithm. This paper studies the message complexity of d…
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…
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
Mélanie Cambus, Fabian Kuhn, Shreyas Pai +1
In this work, we present a constant-round algorithm for the -ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in t…
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…