A TIGHT UPPER BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS

被引：100
作者：
FEIGE, U
机构：
[1] Department of Applied Math, Weizmann Institute, Rehovot
来源：
RANDOM STRUCTURES & ALGORITHMS | 1995年 / 6卷 / 01期
关键词：
D O I：
10.1002/rsa.3240060106
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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.
引用
收藏
页码：51 / 54
页数：4
相关论文
共 8 条
[1]  
Aldous DJ, 1993, REVERSIBLE MARKOV CH
[2]  
Aleliunas R., 1979, 20th Annual Symposium of Foundations of Computer Science, P218, DOI 10.1109/SFCS.1979.34
[3]  
Brightwell G. R., 1990, RANDOM STRUCT ALG, V1, P263, DOI 10.1002/rsa.3240010303
[4]  
CHANDRA AK, 1989, 21ST P ANN ACM S THE, P574, DOI DOI 10.1145/73007.73062
[5]  
COPPERSMITH D, IN PRESS SIAM J DISC
[6]  
DOYLE PG, 1984, RANDOM WALKS ELECTRI
[7]  
FOSTER RM, 1949, CONTRIBUTIONS APPL M, P333
[8]  
Tetali P., 1991, J THEOR PROBAB, V4, P101, DOI DOI 10.1007/BF01046996
1