Short random walks on graphs

被引：20
|
作者：
Barnes, G
Feige, U
机构：
[1] MAX PLANCK INST INFORMAT, SAARBRUCKEN, GERMANY
[2] WEIZMANN INST SCI, DEPT MATH APPL, IL-76100 REHOVOT, ISRAEL
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 1996年 / 9卷 / 01期
关键词：
random walk; graph; Markov chain;
D O I：
10.1137/S0895480194264988
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The short-term behavior of random walks on graphs is studied, in particular, the rate at which a random walk discovers new vertices and edges. A conjecture by Linial, that the expected time to find N distinct vertices is O(N-3) is proved. In addition, upper bounds of O(M(2)) on the expected time to traverse M edges and of O(MN) on the expected time to either visit N vertices or traverse M edges (whichever comes first) are proved.
引用
收藏
页码：19 / 28
页数：10
相关论文
共 50 条
12345