A TIGHT LOWER-BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS
A TIGHT LOWER-BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS
复制标题
DOI：
10.1002/rsa.3240060406
复制
发表时间：
1995-07-01
影响因子：
1
通讯作者：
FEIGE, U
中科院分区：
文献类型：
--
作者：
FEIGE, U
我们证明，覆盖图的所有N顶点的随机步行的预期时间至少为（1 + O（1））N Ln n。 （c）1995 John Wiley＆Sons，Inc。
We prove that the expected time for a random walk to cover all n vertices of a graph is at least (1 + o(1))n ln n. (C) 1995 John Wiley & Sons, Inc.