Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model

Leonid Barenboim, Uri Goldenberg

We obtain improved distributed algorithms in the CONGEST message-passing setting for problems on power graphs of an input graph $G$. This includes Coloring, Maximal Independent Set…