文章基本信息

标题：Coloring Fast Without Learning Your Neighbors' Colors
本地全文：下载
作者：Magnús M. Halldórsson ; Fabian Kuhn ; Yannic Maus 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-17
DOI：10.4230/LIPIcs.DISC.2020.39
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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(â^S{log log n})}.
关键词：distributed graph coloring; distance 2 coloring; congestion