Efficient Deterministic Distributed Coloring with Small Bandwidth

DOI10.1145/3382734.3404504MaRDI QIDQ5855242zbMATH OpenOpenAlexWikidataFDO

Authors Philipp Bamberger, Fabian Kuhn, Yannic Maus

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

CONGEST modeldeterministic vertex coloringmassively parallel computation

Mathematics Subject Classification ID

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

Cited in

(16)

• Vertex coloring with communication and local memory constraints in synchronous broadcast networks
• Linial for lists
• Distributed algorithms for fractional coloring
• Robustness: a new form of heredity motivated by dynamic networks
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Distributed Testing of Distance-k Colorings
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Faster deterministic distributed MIS and approximate matching
• Coloring fast without learning your neighbors' colors
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• Distributed symmetry breaking on power graphs via sparsification
• Massively parallel computation in a heterogeneous regime
• Parallel derandomization for coloring
• Optimal (degree+1)-coloring in congested clique

This page was built for publication: Efficient Deterministic Distributed Coloring with Small Bandwidth

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