Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

DOI10.4230/LIPIcs.DISC.2018.39zbMath1497.68568OpenAlexW2898867280MaRDI QIDQ5090932

Hsin-Hao Su, Merav Parter

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9828/pdf/LIPIcs-DISC-2018-39.pdf

zbMATH Keywords

coloringdistributed graph algorithmscongested clique

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (6)

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

Cites Work

• Unnamed Item
• Lessons from the congested clique applied to MapReduce
• Local Computation
• (Delta+1) Coloring in the Congested Clique Model
• Optimal deterministic routing and sorting on the congested clique
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• An optimal distributed (Δ+1)-coloring algorithm?
• 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: Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds