Cover Time and Broadcast Time

Abstract : 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.~\cite{CRRST97} 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$ and minimum degree $\delta$, we have $\mathcal{R}(G)= \Oh(\frac{|E|}{\delta} \cdot \log n)$, where $\mathcal{R}(G)$ denotes the quotient of the cover time and broadcast time. This bound is tight for binary trees and tight up to logarithmic factors for many graphs including hypercubes, expanders and lollipop graphs. \item For any $\delta$-regular (or almost $\delta$-regular) graph $G$ it holds that $\mathcal{R}(G) = \Omega( \frac{\delta^2}{n} \cdot \frac{1}{\log n})$. Together with our upper bound on $\mathcal{R}(G)$, this lower bound strongly confirms the intuition of Chandra et al.~for graphs with minimum degree $\Theta(n)$, since then the cover time equals the broadcast time multiplied by $n$ (neglecting logarithmic factors). \item Conversely, for any $\delta$ we construct almost $\delta$-regular graphs that satisfy $\mathcal{R}(G) = \Oh( \max \{ \sqrt{n},\delta \} \cdot \log^2 n)$. Since any regular expander satisfies $\mathcal{R}(G) = \Theta(n)$, the strong relationship given above does not hold if $\delta$ is polynomially smaller than $n$. \end{itemize} Our bounds also demonstrate that the relationship between cover time and broadcast time is much stronger than the known relationships between any of them and the mixing time (or the closely related spectral gap).
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.373-384, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359667
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 17:10:57
Dernière modification le : vendredi 13 février 2009 - 10:59:58
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:30:23

Fichiers

elsaesser_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359667, version 1
  • ARXIV : 0902.1735

Collections

Citation

Robert Elsässer, Thomas Sauerwald. Cover Time and Broadcast Time. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.373-384, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359667〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

638