Cover Image

Dynamic Graph Coloring: Sequential, Parallel, and Distributed

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ghaffari, Mohsen, Koo, Jaehyun
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
by: Ghaffari, Mohsen, et al.
Published: (2025)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
by: Ghaffari, Mohsen, et al.
Published: (2025)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
by: Ghaffari, Mohsen, et al.
Published: (2026)

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
by: Koo, Jaehyun
Published: (2024)

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
by: Koo, Jaehyun
Published: (2024)

Parallel Dynamic Maximal Matching
by: Ghaffari, Mohsen, et al.
Published: (2024)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
by: Ghaffari, Mohsen, et al.
Published: (2024)

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
by: Ghaffari, Mohsen, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
by: Ghaffari, Mohsen, et al.
Published: (2024)

Parallel Derandomization for Coloring
by: Coy, Sam, et al.
Published: (2023)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
by: Ghaffari, Mohsen, et al.
Published: (2024)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

Distributionally Robust $k$-of-$n$ Sequential Testing
by: Tan, Rayen, et al.
Published: (2026)

Sequentially Swapping Tokens: Further on Graph Classes
by: Kiya, Hironori, et al.
Published: (2022)

HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search
by: Dehghankar, Mohsen, et al.
Published: (2025)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
by: Grunau, Christoph, et al.
Published: (2025)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

Network Design on Undirected Series-Parallel Graphs
by: Bansal, Ishan, et al.
Published: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

Connectivity Labeling in Faulty Colored Graphs
by: Petruschka, Asaf, et al.
Published: (2024)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
by: Chen, Daoyuan, et al.
Published: (2024)

Dynamic Edge Coloring of Forests
by: Kaplan, Haim, et al.
Published: (2026)

On the Complexity of Distributed Edge Coloring and Orientation Problems
by: Brandt, Sebastian, et al.
Published: (2025)

Tree Embedding in High Dimensions: Dynamic and Massively Parallel
by: Goranci, Gramoz, et al.
Published: (2025)

Parallelize Single-Site Dynamics up to Dobrushin Criterion
by: Liu, Hongyang, et al.
Published: (2021)

Online Coloring for Graphs of Large Odd Girth
by: Yoneda, Hirotaka, et al.
Published: (2026)

GraphBLAS Mathematical Opportunities: Parallel Hypersparse, Matrix Based Graph Streaming, and Complex-Index Matrices
by: Jananthan, Hayden, et al.
Published: (2025)

Adaptive Massively Parallel Coloring in Sparse Graphs
by: Latypov, Rustam, et al.
Published: (2024)

DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams
by: Xuan, Wei, et al.
Published: (2025)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Dynamic $(Δ+ 1)$ Vertex Coloring
by: Benson-Tilsen, Noam
Published: (2026)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
by: Ito, Takehiro, et al.
Published: (2025)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)

Parallel Dynamic Spatial Indexes
by: Men, Ziyang, et al.
Published: (2026)

Fast and Efficient Parallel Breadth-First Search with Power-law Graph Transformation
by: Jiang, Zite, et al.
Published: (2020)

Longest Common Extension of a Dynamic String in Parallel Constant Time
by: Albert, Daniel
Published: (2026)

UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
by: De Man, Quinten, et al.
Published: (2026)

A Cut-Matching Game for Constant-Hop Expanders
by: Haeupler, Bernhard, et al.
Published: (2022)