Superfast coloring in CONGEST via efficient color sampling

DOI10.1007/978-3-030-79527-6_5OpenAlexW3177097187MaRDI QIDQ5918634

Alexandre Nolin, Magnús M. Halldórsson

Publication date: 22 March 2022

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Related Items (1)

Distributed Symmetry Breaking on Power Graphs via Sparsification

Cites Work

• Unnamed Item
• Unnamed Item
• Private vs. common random bits in communication complexity
• Near-optimal, distributed edge colouring via the nibble method
• Simple distributed \(\Delta+1\)-coloring of graphs
• The Locality of Distributed Symmetry Breaking
• Locality in Distributed Graph Algorithms
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Nearly optimal distributed edge coloring in O(log log n) rounds
• Balls and bins: A study in negative dependence
• Communication Complexity
• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• A new technique for distributed symmetry breaking
• Communication Complexity
• Distributed (∆+1)-coloring in sublogarithmic rounds
• (2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Superfast coloring in CONGEST via efficient color sampling