1 citations · 1 across the 4 of their papers we have counts for
4 papers
Parallel Dynamic Maximal Matching
Mohsen Ghaffari, Anton Trygub
We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion o…
A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
Mohsen Ghaffari, Anton Trygub
We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in rounds and each…
A Near-Optimal Deterministic Distributed Synchronizer
Mohsen Ghaffari, Anton Trygub
We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm $\mathca…
Full Characterization of Color Degree Sequences in Complete Graphs Without Tricolored Triangles
Anton Trygub
For an edge-colored complete graph, we define the color degree of a node as the number of colors appearing on edges incident to it. In this paper, we consider colorings that don't…