Random walks on graphs and Monte Carlo methods

被引：6

作者：

Cheng, Wen-Ju ^{[1
]}

Cox, Jim ^{[2
]}

Whitlock, Paula ^{[2
]}

机构：

[1] CUNY, Grad Ctr, Comp Sci, Fifth Ave, New York, NY USA

[2] CUNY Brooklyn Coll, CIS Dept, 2900 Bedford Ave, Brooklyn, NY 11210 USA

来源：

MATHEMATICS AND COMPUTERS IN SIMULATION | 2017年 / 135卷

关键词：

Graph theory; Random walks; Markov chain Monte Carlo; DIRECTED-GRAPHS;

D O I：

10.1016/j.matcom.2015.12.006

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper relates the study of random walks on graphs and directed graphs to random walks that arise in Monte Carlo methods applied to optimization problems. Previous results on simple graphs are surveyed and new results on the mixing times for Markov chains are derived. (C) 2016 International Association for Mathematics and Computers in Simulation (IMACS). Published by Elsevier B.V. All rights reserved.

引用

页码：86 / 94

页数：9

共 14 条

[1]

[Anonymous], 1984, CARUS MATH MONOGR

[2]

[Anonymous], 2004, ELECT C COMPUTATIONA, DOI [DOI 10.1145/1060590.1060647, 10.1145/1060590.1060647]

[3] An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs [J].

Armoni, R ;

Ta-Shma, A ;

Wigderson, A ;

Zhou, SY .

JOURNAL OF THE ACM, 2000, 47 (02) :294-311

[4] PERCOLATION THEORY ON DIRECTED GRAPHS [J].

ARROWSMITH, DK ;

ESSAM, JW .

JOURNAL OF MATHEMATICAL PHYSICS, 1977, 18 (02) :235-238

[5]

Chandra A. K., 1996, Computational Complexity, V6, P312, DOI 10.1007/BF01270385

[6]

Chandra A. K., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P574, DOI 10.1145/73007.73062

[7]

Cheng W.-J., 2014, P 10 INT C THEOR ASP, V8049

[8] Laplacians and the Cheeger inequality for directed graphs [J].

Chung, Fan .

ANNALS OF COMBINATORICS, 2005, 9 (01) :1-19

[9] S-T Connectivity on Digraphs with a Known Stationary Distribution [J].

Chung, Kai-Min ;

Reingold, Omer ;

Vadhan, Salil .

ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (03)

[10] A TIGHT UPPER BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS [J].

FEIGE, U .

RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (01) :51-54

← 1 2 →