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

massively parallel computationCONGEST modeldeterministic vertex coloring

Mathematics Subject Classification ID

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

Cited in

(15)

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

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)