Message Reduction in the LOCAL Model is a Free Lunch
Shimon Bitton, Yuval Emek, Taisuke Izumi, Shay Kutten · 2019
A new spanner construction algorithm is presented, working under the LOCAL model assuming unique edge IDs. Given an n-node communication graph, a spanner with a constant stretch and Õ(n1 + c) edges (for any small constant c > 0) is constructed efficiently --- i.e., in a constant number of rounds and a message complexity of Õ (n1 + 2c) whp.