Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond

Mohsen Ghaffari, Julian Portmann

Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and Plotkin [FOCS'89], are one of the key algorithmic tools in distributed graph algorithms. We present an improv…