{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:04Z","timestamp":1759638544786,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["755839"],"award-info":[{"award-number":["755839"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001840","name":"Icelandic Centre for Research","doi-asserted-by":"publisher","award":["174484 and 217965"],"award-info":[{"award-number":["174484 and 217965"]}],"id":[{"id":"10.13039\/501100001840","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538438","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"26-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Overcoming Congestion in Distributed Coloring"],"prefix":"10.1145","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[{"name":"Reykjavik University, Reykjavik, Iceland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandre","family":"Nolin","sequence":"additional","affiliation":[{"name":"Reykjavik University, Reykjavik, Iceland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tigran","family":"Tonoyan","sequence":"additional","affiliation":[{"name":"Krisp Technologies Inc., Yerevan, Armenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","first-page":"1","article-title":"Palette Sparsification Beyond ( + 1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) (LIPIcs, Vol. 176)","volume":"6","author":"Alon Noga","year":"2020","unstructured":"Noga Alon and Sepehr Assadi . 2020 . Palette Sparsification Beyond ( + 1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) (LIPIcs, Vol. 176) . LZI , 6 : 1 -- 6 :22. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.6 10.4230\/LIPIcs.APPROX Noga Alon and Sepehr Assadi. 2020. Palette Sparsification Beyond ( + 1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) (LIPIcs, Vol. 176). LZI, 6:1--6:22. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.6","journal-title":"LZI"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955678"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2979675"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0132-x"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0324-8"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1249527"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1366502"},{"volume-title":"Probabilistic Tools for the Analysis of Randomized Optimization Heuristics","author":"Doerr Benjamin","key":"e_1_3_2_2_12_1","unstructured":"Benjamin Doerr . 2020. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics . Springer International Publishing , Cham , 1--87. https: \/\/doi.org\/10.1007\/978--3-030--29414--4_1 10.1007\/978--3-030--29414--4_1 Benjamin Doerr. 2020. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics. Springer International Publishing, Cham, 1--87. https: \/\/doi.org\/10.1007\/978--3-030--29414--4_1"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_3_2_2_14_1","article-title":"Distributed Detection of Cycles","volume":"6","author":"Fraigniaud Pierre","year":"2019","unstructured":"Pierre Fraigniaud and Dennis Olivetti . 2019 . Distributed Detection of Cycles . ACM Transactions on Parallel Computing (TOPC) 6 , 3 (2019), 12:1--12:20. https: \/\/doi.org\/10.1145\/3322811 10.1145\/3322811 Pierre Fraigniaud and Dennis Olivetti. 2019. Distributed Detection of Cycles. ACM Transactions on Parallel Computing (TOPC) 6, 3 (2019), 12:1--12:20. https: \/\/doi.org\/10.1145\/3322811","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_25"},{"key":"e_1_3_2_2_16_1","volume-title":"Proc. Symp. on Foundations of Computer Science (FOCS). IEEE, 1009--1020","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2021 . Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition . In Proc. Symp. on Foundations of Computer Science (FOCS). IEEE, 1009--1020 . https:\/\/doi.org\/10. 1109\/FOCS52979.2021.00101 Mohsen Ghaffari and Fabian Kuhn. 2021. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. In Proc. Symp. on Foundations of Computer Science (FOCS). IEEE, 1009--1020. https:\/\/doi.org\/10. 1109\/FOCS52979.2021.00101"},{"key":"e_1_3_2_2_17_1","volume-title":"Proc. Int. Symp. on Distributed Computing (DISC) (LIPIcs","volume":"17","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2020","unstructured":"Magn\u00fas M. Halld\u00f3rsson , Fabian Kuhn , Yannic Maus , and Alexandre Nolin . 2020 . Coloring Fast Without Learning Your Neighbors' Colors . In Proc. Int. Symp. on Distributed Computing (DISC) (LIPIcs , Vol. 179). LZI, 39:1--39: 17 . https:\/\/doi.org\/ 10.4230\/LIPIcs.DISC.2020.39 10.4230\/LIPIcs.DISC.2020.39 Magn\u00fas M. Halld\u00f3rsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin. 2020. Coloring Fast Without Learning Your Neighbors' Colors. In Proc. Int. Symp. on Distributed Computing (DISC) (LIPIcs, Vol. 179). LZI, 39:1--39:17. https:\/\/doi.org\/ 10.4230\/LIPIcs.DISC.2020.39"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325"},{"key":"e_1_3_2_2_19_1","volume-title":"Near-Optimal Distributed Degree+1 Coloring. CoRR abs\/2112.00604","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2021","unstructured":"Magn\u00fas M. Halld\u00f3rsson , Fabian Kuhn , Alexandre Nolin , and Tigran Tonoyan . 2021. Near-Optimal Distributed Degree+1 Coloring. CoRR abs\/2112.00604 ( 2021 ), 44 pages. https:\/\/doi.org\/10.48550\/arXiv.2112.00604 10.48550\/arXiv.2112.00604 Magn\u00fas M. Halld\u00f3rsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. 2021. Near-Optimal Distributed Degree+1 Coloring. CoRR abs\/2112.00604 (2021), 44 pages. https:\/\/doi.org\/10.48550\/arXiv.2112.00604"},{"key":"e_1_3_2_2_20_1","volume-title":"Halld\u00f3rsson and Alexandre Nolin","author":"Magn\u00fas","year":"2021","unstructured":"Magn\u00fas M. Halld\u00f3rsson and Alexandre Nolin . 2021 . Superfast Coloring in CONGEST via Efficient Color Sampling. In Proc. Int. Coll. on Structural Information and Communication Complexity (SIROCCO) (LNCS , Vol. 12810). Springer, 68-- 83 . https:\/\/doi.org\/10.1007\/978--3-030--79527--6_5 10.1007\/978--3-030--79527--6_5 Magn\u00fas M. Halld\u00f3rsson and Alexandre Nolin. 2021. Superfast Coloring in CONGEST via Efficient Color Sampling. In Proc. Int. Coll. on Structural Information and Communication Complexity (SIROCCO) (LNCS, Vol. 12810). Springer, 68--83. https:\/\/doi.org\/10.1007\/978--3-030--79527--6_5"},{"key":"e_1_3_2_2_21_1","volume-title":"Overcoming Congestion in Distributed Coloring. CoRR abs\/2205.14478","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2022","unstructured":"Magn\u00fas M. Halld\u00f3rsson , Alexandre Nolin , and Tigran Tonoyan . 2022. Overcoming Congestion in Distributed Coloring. CoRR abs\/2205.14478 ( 2022 ), 30 pages. Full version of this paper. Magn\u00fas M. Halld\u00f3rsson, Alexandre Nolin, and Tigran Tonoyan. 2022. Overcoming Congestion in Distributed Coloring. CoRR abs\/2205.14478 (2022), 30 pages. Full version of this paper."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00064-2"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_2_26_1","volume-title":"Proc. Latin American Symp. on Theoretical Informatics (LATIN) (LNCS","volume":"225","author":"Molloy Michael","unstructured":"Michael Molloy and Bruce A. Reed . 1998. Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree . In Proc. Latin American Symp. on Theoretical Informatics (LATIN) (LNCS , Vol. 1380). Springer, 216-- 225 . https: \/\/doi.org\/10.1007\/BFb0054323 10.1007\/BFb0054323 Michael Molloy and Bruce A. Reed. 1998. Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree. In Proc. Latin American Symp. on Theoretical Informatics (LATIN) (LNCS, Vol. 1380). Springer, 216--225. https: \/\/doi.org\/10.1007\/BFb0054323"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1378762.1378763"},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. ACM Symp. on Principles of Distributed Computing (PODC). ACM, 257--266","author":"Schneider Johannes","year":"2010","unstructured":"Johannes Schneider and RogerWattenhofer. 2010 . Anewtechnique for distributed symmetry breaking . In Proc. ACM Symp. on Principles of Distributed Computing (PODC). ACM, 257--266 . https:\/\/doi.org\/10.1145\/1835698.1835760 10.1145\/1835698.1835760 Johannes Schneider and RogerWattenhofer. 2010. Anewtechnique for distributed symmetry breaking. In Proc. ACM Symp. on Principles of Distributed Computing (PODC). ACM, 257--266. https:\/\/doi.org\/10.1145\/1835698.1835760"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Salerno Italy","acronym":"PODC '22"},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538438","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":30,"alternative-id":["10.1145\/3519270.3538438","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538438","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}