Cover Image

Density-Dependent Graph Orientation and Coloring in Scalable MPC

Fuente: arXiv

Saved in:

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

Similar Items

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)

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

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
by: Ghaffari, Mohsen, et al.
Published: (2025)

Fully Scalable MPC Algorithms for Euclidean k-Center
by: Czumaj, Artur, et al.
Published: (2025)

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

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)

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

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

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

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

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

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

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

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

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

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

Maximal Palindromes in MPC: Simple and Optimal
by: Pissis, Solon P.
Published: (2025)

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

Scalable Multilevel and Memetic Signed Graph Clustering
by: Hausberger, Felix, et al.
Published: (2022)

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

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

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

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
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)

Engineering Edge Orientation Algorithms
by: Reinstädtler, H., et al.
Published: (2024)

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

Scalable Similarity Search over Large Attributed Bipartite Graphs
by: Ou, Xi, et al.
Published: (2025)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

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

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

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Fully Scalable MPC Algorithms for Clustering in High Dimension
by: Czumaj, Artur, et al.
Published: (2023)

A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs
by: Zhu, Chenghao, et al.
Published: (2025)

EF(X) Orientations: A Parameterized Complexity Perspective
by: Kanellopoulos, Sotiris, et al.
Published: (2025)

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

BD-Index: Scalable Biharmonic Distance Queries on Large Graphs via Divide-and-Conquer Indexing
by: Pan, Yueyang, et al.
Published: (2025)