Treffer: Optimal (Degree+1)-Coloring in Congested Clique
Title:
Optimal (Degree+1)-Coloring in Congested Clique
Authors:
Contributors:
Sam Coy and Artur Czumaj and Peter Davies and Gopinath Mishra
Publisher Information:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Publication Year:
2023
Collection:
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics )
Subject Terms:
Document Type:
Fachzeitschrift
article in journal/newspaper<br />conference object
File Description:
application/pdf
Language:
English
Relation:
Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.46
DOI:
10.4230/LIPIcs.ICALP.2023.46
Availability:
Accession Number:
edsbas.44AFD738
Database:
BASE
Weitere Informationen
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.