5 papers
Dynamic Graph Coloring: Sequential, Parallel, and Distributed
Mohsen Ghaffari, Jaehyun Koo
We present a simple randomized algorithm that can efficiently maintain a coloring as the graph undergoes edge insertion and deletion updates, where denotes an upper bou…
Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
Mohsen Ghaffari, Jaehyun Koo
This paper presents the first parallel batch-dynamic algorithms for computing spanners and sparsifiers. Our algorithms process any batch of edge insertions and deletions in an -…
Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
Mohsen Ghaffari, Jaehyun Koo
We present the first parallel batch-dynamic algorithm for approximating coreness decomposition with worst-case update times. Given any batch of edge insertions and deletions, our a…
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…