Cover time and broadcast time

DOI10.4230/LIPICS.STACS.2009.1842MaRDI QIDQ5389992zbMATH OpenFDO

Authors Robert Elsässer, Thomas Sauerwald

Publication date 24 April 2012

Full work available at URL https://arxiv.org/abs/0902.1735, http://subs.emis.de/LIPIcs/frontdoor_f5fe.html

zbMATH Keywords

random walkrandomized algorithmscover timebroadcast timeparallel and distributed algorithmsrandomized broadcat algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Random walks on graphs (05C81) Distributed systems (68M14)

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: For any graph $G=(V,E)$ of size $n$ and minimum degree $delta$, we have $mathcalR(G)=Oh(frac|E|deltacdotlogn)$, where $mathcalR(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. For any $delta$-regular (or almost $delta$-regular) graph $G$ it holds that $mathcalR(G)=Omega(fracdelt{a}^{2}ncdotfrac1logn)$. Together with our upper bound on $mathcalR(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). Conversely, for any $delta$ we construct almost $delta$-regular graphs that satisfy $mathcalR(G)=Oh(maxsqrtn,deltacdotlo{g}^{2}n)$. Since any regular expander satisfies $mathcalR(G)=Theta(n)$, the strong relationship given above does not hold if $delta$ is polynomially smaller than $n$. 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).

Recommendations

• On the cover time of random walks on graphs
• On the cover time of dense graphs
• Bounds on the cover time
• A Technique for Lower Bounding the Cover Time
• The evolution of the cover time

Cited in

(5)

• On the cover time of dense graphs
• Tight bounds for coalescing-branching random walks on regular graphs
• Randomized rumour spreading: the effect of the network topology
• scientific article; zbMATH DE number 716161 (Why is no real title available?)
• Rumor spreading and vertex expansion

This page was built for publication: Cover time and broadcast time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5389992)