4 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…
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…