2026-07-22T06:49:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13117 2024-03-06T10:51:36Z ddc:004 open_access

Coloring Fast Without Learning Your Neighbors' Colors Halldórsson, Magnús M. Kuhn, Fabian Maus, Yannic Nolin, Alexandre distributed graph coloring distance 2 coloring congestion We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Magnús M. Halldórsson and Fabian Kuhn and Yannic Maus and Alexandre Nolin 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.39 urn:nbn:de:0030-drops-131170 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.39 eng https://creativecommons.org/licenses/by/3.0/legalcode