EUVIMEDEUVIMED entdecken
Crossref

Optimal (degree+1)-Coloring in Congested Clique

Sam Coy, Artur Czumaj, Peter Davies, Gopinath Mishra

SIAM Journal on Computing · 31.08.2026 · 55 (4) · 521-559

DOI: 10.1137/24m163092x ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 17.07.2026. Verfasst von Sam Coy und 3 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Gefördert von: Centre for Discrete Mathematics and its Applications, Simons Foundation, Engineering and Physical Sciences Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the distributed complexity of the ( degree + 1 )-list coloring problem, in which each node [Formula: see text] of degree [Formula: see text] is assigned a palette of [Formula: see text] 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 [Formula: see text]-coloring and [Formula: see text]-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.

Förderung

  • Centre for Discrete Mathematics and its Applications
  • Simons Foundation
  • Engineering and Physical Sciences Research Council

Zitieren

APA

Coy, S., Czumaj, A., Davies, P., & Mishra, G. (2026). Optimal (degree+1)-Coloring in Congested Clique. SIAM Journal on Computing, 55(4), 521-559. https://doi.org/10.1137/24m163092x

Vancouver

Coy S, Czumaj A, Davies P, Mishra G. Optimal (degree+1)-Coloring in Congested Clique. SIAM Journal on Computing. 2026;55(4):521-559. doi:10.1137/24m163092x

BibTeX
@article{Coy2026,
  author = {Coy, Sam and Czumaj, Artur and Davies, Peter and Mishra, Gopinath},
  title = {Optimal (degree+1)-Coloring in Congested Clique},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {4},
  pages = {521--559},
  doi = {10.1137/24m163092x}
}
Kostenlos starten →