3 papers
cs.DS2025
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…
cs.DC2022
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…
cs.DC2021
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…