CISPA
Browse
LIPIcs.DISC.2023.19.pdf (954.49 kB)

Fast Coloring Despite Congested Relays.

Download (954.49 kB)
preprint
posted on 2024-02-27, 07:51 authored by Maxime Flin, Magnús M Halldórsson, Alexandre NolinAlexandre Nolin
We provide a O(log6logn)-round randomized algorithm for distance-2 coloring in CONGEST with Δ2+1 colors. For Δ≫polylogn, this improves exponentially on the O(logΔ+polyloglogn) algorithm of [Halldórsson, 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ász 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.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

BibTeX

@misc{Flin:Halldórsson:Nolin:2023, title = "Fast Coloring Despite Congested Relays.", author = "Flin, Maxime" AND "Halldórsson, Magnús M" AND "Nolin, Alexandre", year = 2023, month = 8 }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC