Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication
OPEN ACCESS
Loading...
Author / Producer
Date
2019
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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)}.
Permanent link
Publication status
published
External links
Book title
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Volume
132
Pages / Article No.
142
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Distributed Computing; Message Passing Algorithms; Graph Coloring; Arboricity; Congested Clique Model; Randomized Algorithms
Organisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
Notes
Funding
184735 - Distributed Algorithms for Global Graph Problems (SNF)