Fast coloring despite congested relays
M Flin, MM Halldórsson, A Nolin - arXiv preprint arXiv:2308.01359, 2023 - arxiv.org
M Flin, MM Halldórsson, A Nolin
arXiv preprint arXiv:2308.01359, 2023•arxiv.orgWe provide a $ O (\log^ 6\log n) $-round randomized algorithm for distance-2 coloring in
CONGEST with $\Delta^ 2+ 1$ colors. For $\Delta\gg\operatorname {poly}\log n $, this
improves exponentially on the $ O (\log\Delta+\operatorname {poly}\log\log n) $ algorithm of
[Halld\'orsson, Kuhn, Maus, Nolin, DISC'20]. Our study is motivated by the ubiquity and
hardness of local reductions in CONGEST. For instance, algorithms for the Local Lov\'asz
Lemma [Moser, Tardos, JACM'10; Fischer, Ghaffari, DISC'17; Davies, SODA'23] usually …
CONGEST with $\Delta^ 2+ 1$ colors. For $\Delta\gg\operatorname {poly}\log n $, this
improves exponentially on the $ O (\log\Delta+\operatorname {poly}\log\log n) $ algorithm of
[Halld\'orsson, Kuhn, Maus, Nolin, DISC'20]. Our study is motivated by the ubiquity and
hardness of local reductions in CONGEST. For instance, algorithms for the Local Lov\'asz
Lemma [Moser, Tardos, JACM'10; Fischer, Ghaffari, DISC'17; Davies, SODA'23] usually …
We provide a -round randomized algorithm for distance-2 coloring in CONGEST with colors. For , this improves exponentially on the algorithm of [Halld\'orsson, Kuhn, Maus, Nolin, DISC'20]. Our study is motivated by the ubiquity and hardness of local reductions in CONGEST. For instance, algorithms for the Local Lov\'asz Lemma [Moser, Tardos, JACM'10; Fischer, Ghaffari, DISC'17; Davies, SODA'23] usually assume communication on the conflict graph, which can be simulated in LOCAL with only constant overhead, while this may be prohibitively expensive in CONGEST. We hope our techniques help tackle in CONGEST other coloring problems defined by local relations.
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果