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

DOI10.4230/LIPICS.DISC.2018.39zbMATH Open1497.68568OpenAlexW2898867280MaRDI QIDQ5090932FDOQ5090932

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

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

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)

Cites Work

• Optimal deterministic routing and sorting on the congested clique
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Local Computation
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Lessons from the congested clique applied to MapReduce
• An optimal distributed (Δ+1)-coloring algorithm?
• Title not available (Why is that?)
• (Delta+1) Coloring in the Congested Clique Model
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Distributed MIS via all-to-all communication

Cited In (8)

• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Derandomizing local distributed algorithms under bandwidth restrictions
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Title not available (Why is that?)
• Lessons from the congested clique applied to MapReduce
• Superfast coloring in CONGEST via efficient color sampling
• Fast approximate shortest paths in the congested clique
• Title not available (Why is that?)

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)