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

DOI10.1137/20M1366502OpenAlexW3209631018MaRDI 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

coloringderandomizationmassively parallel computationcongested clique

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (3)

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

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

This page was built for publication: Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC