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

DOI10.4230/LIPICS.DISC.2018.39MaRDI QIDQ5090932zbMATH OpenOpenAlexFDO

Authors Hsin-Hao Su, M. 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)

Recommendations

• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• Simple, Deterministic, Constant-Round Coloring in the Congested Clique
• \((\Delta+1)\) coloring in the congested clique model
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• scientific article; zbMATH DE number 1839472
• Efficient randomized distributed coloring in CONGEST
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• A randomized algorithm for \(k\)-colorability

Cites work

• An optimal distributed \((\Delta+1)\)-coloring algorithm?
• Distributed MIS via all-to-all communication
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Lessons from the congested clique applied to MapReduce
• Local computation: lower and upper bounds
• MST in \(O(1)\) rounds of congested clique
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Optimal deterministic routing and sorting on the congested clique
• \((\Delta+1)\) coloring in the congested clique model

Cited in

(10)

• Distributed symmetry-breaking algorithms for congested cliques
• scientific article; zbMATH DE number 7758308 (Why is no real title available?)
• scientific article; zbMATH DE number 7525452 (Why is no real title available?)
• Lessons from the congested clique applied to MapReduce
• Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
• Fast approximate shortest paths in the congested clique
• \((\Delta+1)\) coloring in the congested clique model
• Derandomizing local distributed algorithms under bandwidth restrictions
• Superfast coloring in CONGEST via efficient color sampling
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC

This page was built for publication: Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds

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