ICS 269, Spring 2022: Theory Seminar
Bren Hall 1423, 1:00 – 1:50


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 \((1+\varepsilon)\)-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.)