Title
(Delta+1) Coloring in the Congested Clique Model.
Abstract
In this paper, we present improved algorithms for the $(Delta+1)$ (vertex) coloring problem the Congested-Clique model of distributed computing. In this model, the input is a graph on $n$ nodes, initially each node knows only its incident edges, and per round each two nodes can exchange $O(log n)$ bits of information. Our key result is a randomized $(Delta+1)$ vertex coloring algorithm that works $O(loglog Delta cdot log^* Delta)$-rounds. This is achieved by combining the recent breakthrough result of [Chang-Li-Pettie, STOCu002718] the local model and a degree reduction technique. We also get the following results with high probability: (1) $(Delta+1)$-coloring for $Delta=O((n/log n)^{1-epsilon})$ for any $epsilon in (0,1)$, within $O(log(1/epsilon)log^* Delta)$ rounds, and (2) $(Delta+Delta^{1/2+o(1)})$-coloring within $O(log^* Delta)$ rounds. Turning to deterministic algorithms, we show a $(Delta+1)$-coloring algorithm that works $O(log Delta)$ rounds.
Year
Venue
Field
2018
ICALP
Delta,Graph,Discrete mathematics,Binary logarithm,Combinatorics,Vertex (geometry),Clique,Mathematics,Coloring problem
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
12
1
Name
Order
Citations
PageRank
Merav Parter116932.59