The cover time of two classes of random graphs
The cover time of two classes of random graphs
复制标题
两类随机图的覆盖时间
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
C. Cooper;A. Frieze
设<i>G</i> =（<i>V，E</i>）是连通图，设|<i>V</i>| = <i>n</i>，且|<i>E</i>| = <i>m。</i>无<i><inf></inf></i><i></i>向图<i>G</i> =（<i>V，E</i>）上的随机游动Wu，u ∈ V是一个马尔可夫链<i>X <inf>0</inf></i> = <i>u，<inf>X1</inf>，. X<inf>t</inf>，. </i>从顶点到顶点移动的粒子，根据以下规则：如果{<i>i，j</i>} ∈<i>E，则</i>从度为<i>di<inf>的</inf></i>顶点<i>i</i>到顶点<i>j</i>的转移概率为1/<i>di<inf></inf></i><i>，</i>否则为0。设<i>u</i> ∈ <i>V</i>，<i><inf>Cu</inf></i>是<i><inf>Wu</inf></i>访问G的每个顶点<i>所需的期望时间. </i>G的<i>覆盖时间CG<inf>定义</inf></i><i></i>为<i><inf>CG</inf></i> = <i>maxu</i> ∈ <i><inf>VCu</inf>. </i>连通图的覆盖时间已经得到了广泛的研究。<i>C<inf>G</inf></i>≤ 2<i>m</i>（<i>n</i>- 1）是Aleliunas，Karp，Lipton，Lovász和Rackoff [2]的经典结果. Feige [11]，[12]证明了对于任何连通图<i>G</i>[EQUATION]，下界可由（例如）完全图<i><inf>Kn</inf></i>达到，其覆盖时间由Coupon Collector问题确定。
Let <i>G</i> = (<i>V,E</i>) be a connected graph, let |<i>V</i>| = <i>n</i>, and |<i>E</i>| = <i>m.</i> <i>A random walk W<inf>u</inf>, u</i> ∈ <i>V</i> on the undirected graph <i>G</i> = (<i>V, E</i>) is a Markov chain <i>X<inf>0</inf></i> = <i>u, X<inf>1</inf>,...X<inf>t</inf>,...</i> ∈ <i>V</i> associated to a particle that moves from vertex to vertex according to the following rule: the probability of a transition from vertex <i>i</i>, of degree <i>d<inf>i</inf></i>, to vertex <i>j</i> is 1/<i>d<inf>i</inf></i> if {<i>i,j</i>} ∈ <i>E</i>, and 0 otherwise. For <i>u</i> ∈ <i>V</i> let <i>C<inf>u</inf></i> be the expected time taken for <i>W<inf>u</inf></i> to visit every vertex of <i>G.</i> The <i>cover time C<inf>G</inf></i> of <i>G</i> is defined as <i>C<inf>G</inf></i> = max<i>u</i>∈<i>V C<inf>u</inf>.</i> The cover time of connected graphs has been extensively studied. It is a classic result of Aleliunas, Karp, Lipton, Lovász and Rackoff [2] that <i>C<inf>G</inf></i> ≤ 2<i>m</i>(<i>n</i> - 1). It was shown by Feige [11], [12], that for any connected graph <i>G</i>[EQUATION]The lower bound is achieved by (for example) the complete graph <i>K<inf>n</inf></i>, whose cover time is determined by the Coupon Collector problem.