Time-Optimal Construction of Overlay Networks

Thorsten Götte, Kristian Hinnenthal, Christian Scheideler +1

We show how to construct an overlay network of constant degree and diameter $O(\log n)$ in time $O(\log n)$ starting from an arbitrary weakly connected graph. We assume a synchrono…