Cover Time and Broadcast Time

Robert ElsäSser & Thomas Sauerwald
We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. (1997) that ``the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms''. In more detail, our results are as follows: \begin{itemize} \item For any graph $G=(V,E)$ of size $n$...