Cover Time and Broadcast Time
Cover Time and Broadcast Time
复制标题
封面时间和播出时间
DOI：
10.4230/lipics.stacs.2009.1842
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Thomas Sauerwald
中科院分区：
文献类型：
--
作者：
Robert Elsässer;Thomas Sauerwald
通过将随机行走覆盖时间与随机广播的运行时间联系起来，提出了一种限定随机行走覆盖时间的新技术。特别是，对于密集图，我们强烈确认钱德拉等人\cite{CRRST97}的直觉，即“图的覆盖时间是某些随机广播算法性能的适当度量”。更详细地说，我们的结果如下：对于任何大小为$n$和最小度为$\delta$的图$G=(V,E)$，我们有$\mathcal{R}(G)= \Oh(\frac{|E|}{\delta} \cdot \log n)$，其中$\mathcal{R}(G)$表示覆盖时间和广播时间的商。这个界对于二叉树是紧的，对于许多图，包括超立方体、扩展图和棒棒糖图，它的对数因子是紧的。对于任何$\delta$ -正则（或几乎$\delta$ -正则）图$G$，它持有$\mathcal{R}(G) = \Omega(\frac{\delta^2}{n} \cdot \frac{1}{\log n})$。与我们在$\mathcal{R}(G)$上的上界一起，这个下界有力地证实了钱德拉等人对最小度$\Theta(n)$图的直觉，因为那时的覆盖时间等于广播时间乘以$n$（忽略对数因素）。相反，对于任何$\delta$，我们构造几乎满足$\mathcal{R}(G) = \Oh(\max \{\sqrt{n},\delta \} \cdot \log^2 n)$的$\delta$正则图。因为任何正则展开器都满足$\mathcal{R}(G) = \Theta(n)$，所以如果$\delta$多项式地小于$n$，上述强关系就不成立。我们的边界还表明，覆盖时间和广播时间之间的关系比它们与混合时间（或密切相关的频谱间隙）之间的已知关系强得多。
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 $\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. 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). 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$. 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).