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

共 24 条

[1]

AJTAI M, 1987, 19TH P ACM S THEOR C, P132

[2]

Aldous DJ., 1988, J THEORET PROBAB, V2, P91, DOI [DOI 10.1007/BF01048272, 10.1007/BF01048272]

[3]

Aleliunas R., 1979, 20th Annual Symposium of Foundations of Computer Science, P218, DOI 10.1109/SFCS.1979.34

[4]

[Anonymous], 1993, REVERSIBLE MARKOV CH

[5]

Barnes G., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P728, DOI 10.1145/167088.167275

[6]

BRODER A, 1989, J THEORET PROBAB, V2, P101

[7]

Broder A. Z., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P543, DOI 10.1145/73007.73059

[8]

Broder Andrei Z., 1988, P 20 ANN ACM S THEOR, P551

[9]

BRODER AZ, 1986, 18TH P ACM S THEOR C, P50

[10]

CHANDRA AK, 1989, 21ST P ANN ACM S THE, P574

← 1 2 3 →