3 June 2022: Hadi Khodabandeh
Spanner construction for unit ball graphs in the CONGEST model of distributed computation
We first introduce a LOCAL algorithm for finding light weight
-spanners for unit ball graphs in doubling spaces. We
elaborate how it would be challenging to adjust this distributed
algorithm to work in the CONGEST model, and we show how to overcome this
challenge and design an algorithm with the same asymptotic round
complexity in the CONGEST model.
(Joint work with David Eppstein.)