Optimal (degree+1)-Coloring in Congested Clique
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914400228605952 |
|---|---|
| author | Coy, Sam Czumaj, Artur Davies, Peter Mishra, Gopinath |
| author_facet | Coy, Sam Czumaj, Artur Davies, Peter Mishra, Gopinath |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_12071 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal (degree+1)-Coloring in Congested Clique Coy, Sam Czumaj, Artur Davies, Peter Mishra, Gopinath Data Structures and Algorithms 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. |
| title | Optimal (degree+1)-Coloring in Congested Clique |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2306.12071 |