2026-08-08T11:24:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10718 2024-03-06T10:46:33Z ddc:004 open_access

Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication Ghaffari, Mohsen Sayyadi, Ali Distributed Computing Message Passing Algorithms Graph Coloring Arboricity Congested Clique Model Randomized Algorithms We present a constant-time randomized distributed algorithms in the congested clique model that computes an O(alpha)-vertex-coloring, with high probability. Here, alpha denotes the arboricity of the graph, which is, roughly speaking, the edge-density of the densest subgraph. Congested clique is a well-studied model of synchronous message passing for distributed computing with all-to-all communication: per round each node can send one O(log n)-bit message algorithm to each other node. Our O(1)-round algorithm settles the randomized round complexity of the O(alpha)-coloring problem. We also explain that a similar method can provide a constant-time randomized algorithm for decomposing the graph into O(alpha) edge-disjoint forests, so long as alpha <= n^{1-o(1)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohsen Ghaffari and Ali Sayyadi 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.142 urn:nbn:de:0030-drops-107187 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.142 eng https://creativecommons.org/licenses/by/3.0/legalcode