Coy, Sam, Czumaj, Artur, Davies, Peter and Mishra, Gopinath (2023) Optimal (degree+1)-coloring in congested clique. In: ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming, Paderborn, Germany, 10-14 Jul 2023. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 261 45:1-45:16. ISBN 9783959772785. doi:10.4230/LIPIcs.ICALP.2023.45 ISSN 1868-8969.
Preview |
PDF
WRAP-optimal-(degree+1)-coloring-congested-clique-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1MB) | Preview |
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.
| Item Type: | Conference Item (Paper) |
|---|---|
| Alternative Title: | |
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Library of Congress Subject Headings (LCSH): | Electronic data processing -- Distributed processing, Graph coloring, Parallel computers -- Research |
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) |
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik |
| ISBN: | 9783959772785 |
| ISSN: | 1868-8969 |
| Official Date: | 2023 |
| Dates: | Date Event 2023 Available 21 April 2023 Accepted |
| Volume: | 261 |
| Page Range: | 45:1-45:16 |
| DOI: | 10.4230/LIPIcs.ICALP.2023.45 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Open Access (Creative Commons open licence) |
| Date of first compliant deposit: | 21 June 2023 |
| Date of first compliant Open Access: | 22 June 2023 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick UNSPECIFIED [EPSRC] Engineering and Physical Sciences Research Council EP/V01305X/1 [EPSRC] Engineering and Physical Sciences Research Council |
| Conference Paper Type: | Paper |
| Title of Event: | ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming |
| Type of Event: | Conference |
| Location of Event: | Paderborn, Germany |
| Date(s) of Event: | 10-14 Jul 2023 |
| Related URLs: | |
| URI: | https://wrap.warwick.ac.uk/176731/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |