The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

DOI10.1145/3293611.3331607OpenAlexW2962677563MaRDI QIDQ5145259FDOQ5145259

Authors: Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, Yufan Zheng 

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.08419

Recommendations

• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• \((\Delta+1)\) coloring in the congested clique model
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds

zbMATH Keywords

coloringmassively parallel computationcongested cliquecentralized local computation

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (15)

• Title not available (Why is that?)
• Derandomizing local distributed algorithms under bandwidth restrictions
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Distributed-prover interactive proofs
• Equivalence classes and conditional hardness in massively parallel computations
• Title not available (Why is that?)
• The hardness of optimization problems on the weighted massively parallel computation model
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Maliciously secure massively parallel computation for all-but-one corruptions
• Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
• Distributed coloring of hypergraphs
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Near-optimal clustering in the \(k\)-machine model
• Title not available (Why is that?)
• Component stability in low-space massively parallel computation

This page was built for publication: The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145259)