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