License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.46
URN: urn:nbn:de:0030-drops-180987
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18098/
Go to the corresponding LIPIcs Volume Portal

Coy, Sam ; Czumaj, Artur ; Davies, Peter ; Mishra, Gopinath

Optimal (Degree+1)-Coloring in Congested Clique

pdf-format:
LIPIcs-ICALP-2023-46.pdf (1.0 MB)

Abstract

We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u)+1 colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list coloring problem is a natural generalization of the classical (Δ+1)-coloring and (Δ+1)-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing.
In this paper we settle the complexity of the (degree+1)-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.

BibTeX - Entry

@InProceedings{coy_et_al:LIPIcs.ICALP.2023.46,
  author =	{Coy, Sam and Czumaj, Artur and Davies, Peter and Mishra, Gopinath},
  title =	{{Optimal (Degree+1)-Coloring in Congested Clique}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18098},
  URN =		{urn:nbn:de:0030-drops-180987},
  doi =		{10.4230/LIPIcs.ICALP.2023.46},
  annote =	{Keywords: Distributed computing, graph coloring, parallel computing}
}

Keywords: Distributed computing, graph coloring, parallel computing
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI