---
res:
bibo_abstract:
- 'We settle the complexity of the (∆ + 1)-coloring and (∆ + 1)-list coloring problems
intheCONGESTED CLIQUEmodel by presenting a simpledeterministicalgorithm for both
problemsrunning in a constant number of rounds. This matches the complexity of
the recent breakthroughrandomizedconstant-round (∆ + 1)-list coloring algorithm
due to Chang et al. [Proceedings of the38th ACM Symposium on Principles of Distributed Computing, 2019] and significantly improvesupon
the state-of-the-artO(log ∆)-round deterministic (∆ + 1)-coloring bound of Parter
[Proceed-ings of the 45th Annual International Colloquium on Automata, Languages
and Programming]. Aremarkable property of our algorithm is its simplicity. Whereas
the state-of-the-artrandomizedal-gorithms for this problem are based on the quite
involved local coloring algorithm of Chang, Li, andPettie [Proceedings of the
50th Annual ACM SIGACT Symposium on Theory of Computing, 2018],our algorithm can
be described in just a few lines. At a high level, it applies a careful derandomiza-tion
of a recursive procedure which partitions the nodes and their respective palettes
into separatebins. We show that afterO(1) recursion steps, the remaining uncolored
subgraph within each bin haslinear size and thus can be solved locally by collecting
it to a single node. This algorithm can alsobe implemented in the massively parallel
computation (MPC) model provided that each machine haslinear (inn, the number
of nodes in the input graph) space. We also show an extension of our algo-rithm
to theMPCregime, in which machines havesublinearspace: we present the first deterministic(∆
+ 1)-list coloring algorithm designed for sublinear-spaceMPC, which runs inO(log
∆ + log logn)rounds.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Artur
foaf_name: Czumaj, Artur
foaf_surname: Czumaj
- foaf_Person:
foaf_givenName: Peter
foaf_name: Davies, Peter
foaf_surname: Davies
foaf_workInfoHomepage: http://www.librecat.org/personId=11396234-BB50-11E9-B24C-90FCE5697425
orcid: 0000-0002-5646-9524
- foaf_Person:
foaf_givenName: Merav
foaf_name: Parter, Merav
foaf_surname: Parter
bibo_doi: 10.1137/20m1366502
bibo_issue: '5'
bibo_volume: 50
dct_date: 2021^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0097-5397
- http://id.crossref.org/issn/1095-7111
dct_language: eng
dct_publisher: Society for Industrial & Applied Mathematics@
dct_subject:
- General Mathematics
- General Computer Science
dct_title: Simple, deterministic, constant-round coloring in congested clique and
MPC@
...