A TIGHT UPPER BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS
A TIGHT UPPER BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS
复制标题
DOI：
10.1002/rsa.3240060106
复制
发表时间：
1995-01-01
影响因子：
1
通讯作者：
FEIGE, U
中科院分区：
文献类型：
--
作者：
FEIGE, U
我们证明随机游走访问连通图的所有 n 个顶点的预期时间最多为 4/27 n3 + o(n3)。 (C) 1995 约翰威利父子公司
We prove that the expected time for a random walk to visit all n vertices of a connected graph is at most 4/27 n3 + o(n3). (C) 1995 John Wiley & Sons, Inc.