Distributed Symmetry-Breaking with Improved Vertex-Averaged Complexity

Leonid Barenboim, Yaniv Tzur

We study the distributed message-passing model in which a communication network is represented by a graph G=(V,E). Usually, the measure of complexity that is considered in this mod…