Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC

DOI10.1137/20M1366502MaRDI QIDQ5860478

Peter Davies, Merav Parter, Artur Czumaj

Publication date: 19 November 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1366502

zbMATH Keywords

coloring; derandomization; massively parallel computation; congested clique

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68M14: Distributed systems

68W15: Distributed algorithms

Related Items

Superfast coloring in CONGEST via efficient color sampling, Component stability in low-space massively parallel computation, Distributed coloring of hypergraphs

Uses Software

• MapReduce
• Hadoop
• Dryad
• Spark

Cites Work

• Unnamed Item
• Distributed symmetry-breaking algorithms for congested cliques
• Derandomizing local distributed algorithms under bandwidth restrictions
• Sorting, Searching, and Simulation in the MapReduce Framework
• Improved Distributed Approximate Matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Communication-Efficient Parallel Sorting
• A Fast Derandomization Scheme and Its Applications
• (Delta+1) Coloring in the Congested Clique Model
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• Optimal deterministic routing and sorting on the congested clique
• An optimal distributed (Δ+1)-coloring algorithm?
• Efficient Deterministic Distributed Coloring with Small Bandwidth