(Delta+1) Coloring in the Congested Clique Model

DOI10.4230/LIPIcs.ICALP.2018.160zbMath1498.68372arXiv1805.02457OpenAlexW2963747089MaRDI QIDQ5002850

Merav Parter

Publication date: 28 July 2021

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

zbMATH Keywords

coloringdistributed graph algorithmscongested clique

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

Related Items (7)

Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds ⋮ Fast approximate shortest paths in the congested clique ⋮ Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC

Cites Work

• Lessons from the congested clique applied to MapReduce
• Super-Fast Distributed Algorithms for Metric Facility Location
• Local Computation
• The Locality of Distributed Symmetry Breaking
• An algorithmic approach to the Lovász local lemma. I
• An Improved Distributed Algorithm for Maximal Independent Set
• What Can be Computed Locally?
• On the complexity of local distributed graph problems
• Optimal deterministic routing and sorting on the congested clique
• A new technique for distributed symmetry breaking
• Distributed (∆+1)-coloring in sublogarithmic rounds
• Distributed MIS via All-to-All Communication
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

This page was built for publication: (Delta+1) Coloring in the Congested Clique Model