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

Fast Coloring Despite Congested Relays.

Download (954.49 kB)
conference contribution
posted on 2024-02-27, 07:51 authored by Maxime Flin, Magnús M Halldórsson, Alexandre 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

Editor

Oshman R

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

DISC International Symposium on Distributed Computing (DISC)

Journal

DISC

Volume

281

Page Range

19:1-19:1

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

BibTeX

@conference{Flin:Halldórsson:Nolin:2023, title = "Fast Coloring Despite Congested Relays.", author = "Flin, Maxime" AND "Halldórsson, Magnús M" AND "Nolin, Alexandre", editor = "Oshman, Rotem", year = 2023, month = 10, journal = "DISC", pages = "19:1--19:1", publisher = "Schloss Dagstuhl - Leibniz-Zentrum für Informatik" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC