Overcoming Congestion in Distributed Coloring

DOI10.1145/3519270.3538438MaRDI QIDQ6201994zbMATH OpenWikidataFDO

Authors Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan

Publication date 26 March 2024

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

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

zbMATH Keywords

congest modeldistributed graph coloringpseudorandomness

Mathematics Subject Classification ID

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

Abstract: We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm for $(operatornamedegree+1)$-list-coloring (D1LC), this allows us to solve D1LC in $O(lo{g}^{5}logn)$ CONGEST rounds, and in only $O(lo{g}^{\ast }n)$ rounds when the graph has minimum degree $Omega(lo{g}^{7}n)$, w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in $O(1)$ CONGEST rounds, w.h.p.

Cited in

(2)

• Parallel derandomization for coloring
• Optimal (degree+1)-coloring in congested clique

This page was built for publication: Overcoming Congestion in Distributed Coloring

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