2 papers
cs.DS2024
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…
cs.DS2024
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…