(δ+1) Vertex Coloring in O(n) Communication
| dc.contributor.author | Flin, Maxime | |
| dc.contributor.author | Mittal, Parth | |
| dc.contributor.department | Department of Computer Science | |
| dc.date.accessioned | 2026-10-15T11:12:01Z | |
| dc.date.available | 2026-10-15T11:12:01Z | |
| dc.date.issued | 2024-06-17 | |
| dc.description | Publisher Copyright: © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM. | en |
| dc.description.abstract | We study the communication complexity of (Δ+ 1) vertex coloring, where the edges of an n-vertex graph of maximum degree Δare partitioned between two players. We provide a randomized protocol which uses O(n) bits of communication and ends with both players knowing the coloring. Combining this with a folklore ω(n) lower bound, this settles the randomized communication complexity of (Δ+ 1)-coloring up to constant factors. | en |
| dc.description.version | Peer reviewed | en |
| dc.format.extent | 9 | |
| dc.format.extent | 571137 | |
| dc.format.extent | 416-424 | |
| dc.format.extent | ||
| dc.identifier.citation | Flin, M & Mittal, P 2024, (δ+1) Vertex Coloring in O(n) Communication. in PODC 2024 - Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 416-424, 43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, 17/06/24. https://doi.org/10.1145/3662158.3662796 | en |
| dc.identifier.citation | conference | en |
| dc.identifier.doi | 10.1145/3662158.3662796 | |
| dc.identifier.isbn | 9798400706684 | |
| dc.identifier.other | 251327062 | |
| dc.identifier.other | 064392c9-dba2-4e4d-a197-05f040c3dec8 | |
| dc.identifier.other | 85199052109 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.11815/8767 | |
| dc.language.iso | en | |
| dc.publisher | Association for Computing Machinery | |
| dc.relation.ispartofseries | PODC 2024 - Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing; () | en |
| dc.relation.ispartofseries | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; () | en |
| dc.relation.url | https://www.scopus.com/pages/publications/85199052109 | en |
| dc.rights | info:eu-repo/semantics/openAccess | en |
| dc.subject | coloring | en |
| dc.subject | communication complexity | en |
| dc.subject | sparsification | en |
| dc.subject | Software | en |
| dc.subject | Hardware and Architecture | en |
| dc.subject | Computer Networks and Communications | en |
| dc.title | (δ+1) Vertex Coloring in O(n) Communication | en |
| dc.type | /dk/atira/pure/researchoutput/researchoutputtypes/contributiontobookanthology/conference | en |
Skrár
Original bundle
1 - 1 af 1
- Nafn:
- 3662158.3662796.pdf
- Stærð:
- 557.75 KB
- Snið:
- Adobe Portable Document Format