Distributed coloring of hypergraphs

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

Unnamed Item
Unnamed Item
Linial for lists
On graph problems in a semi-streaming model
The Locality of Distributed Symmetry Breaking
Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
A constructive proof of the general lovász local lemma
Locality in Distributed Graph Algorithms
An Improved Distributed Algorithm for Maximal Independent Set
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
A Time Hierarchy Theorem for the LOCAL Model
Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
Polylogarithmic-time deterministic network decomposition and distributed derandomization
An Automatic Speedup Theorem for Distributed Problems
The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
Optimal deterministic routing and sorting on the congested clique
A new technique for distributed symmetry breaking
Sublinear Algorithms for (Δ + 1) Vertex Coloring
A lower bound for the distributed Lovász local lemma
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
Distributed algorithms for the Lovász local lemma and graph coloring
Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
Near-optimal distributed degree+1 coloring
Distributed ∆-coloring plays hide-and-seek