Paper Info

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 |

Authors (1 rows)

Cited by (0 rows)

References (12 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Merav Parter | 1 | 169 | 32.59 |