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

DOI10.1145/3293611.3331607OpenAlexW2962677563MaRDI QIDQ5145259

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

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

zbMATH Keywords

coloringmassively parallel computationcongested cliquecentralized local computation

Mathematics Subject Classification ID

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

Related Items (13)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Deterministic Massively Parallel Connectivity ⋮ Component stability in low-space massively parallel computation ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC

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