On the mean and variance of cover times for random walks on graphs

被引：0
|
作者：
Ball, F [1 ]
Dunham, B [1 ]
Hirschowitz, A [1 ]
机构：
[1] UNIV EDINBURGH,DEPT COMP SCI,EDINBURGH EH9 3JZ,MIDLOTHIAN,SCOTLAND
来源：
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS | 1997年 / 207卷 / 02期
关键词：
D O I：
10.1006/jmaa.1997.5298
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A method is described for calculating the mean cover time for a particle performing a simple random walk on the vertices of a finite connected graph. The method also yields the variance and generating function of the cover time. A computer program is available which utilises the approach to provide results for vertex symmetric graphs. Some examples are given. (C) 1997 Academic Press.
引用
收藏
页码：506 / 514
页数：9
相关论文
共 50 条
  • [1] Analytical results for the distribution of cover times of random walks on random regular graphs
    Tishby, Ido
    Biham, Ofer
    Katzav, Eytan
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2022, 55 (01)
  • [2] On the cover time for random walks on random graphs
    Jonasson, J
    COMBINATORICS PROBABILITY & COMPUTING, 1998, 7 (03): : 265 - 279
  • [3] The Cover Times of Random Walks on Hypergraphs
    Cooper, Colin
    Frieze, Alan
    Radzik, Tomasz
    STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, 2011, 6796 : 210 - 221
  • [4] EXPECTED HITTING AND COVER TIMES OF RANDOM-WALKS ON SOME SPECIAL GRAPHS
    PALACIOS, JL
    RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (01) : 173 - 182
  • [5] Meeting times of random walks on graphs
    Bshouty, NH
    Higham, L
    Warpechowska-Gruca, J
    INFORMATION PROCESSING LETTERS, 1999, 69 (05) : 259 - 265
  • [6] The cover times of random walks on random uniform hypergraphs
    Cooper, Colin
    Frieze, Alan
    Radzik, Tomasz
    THEORETICAL COMPUTER SCIENCE, 2013, 509 : 51 - 69
  • [7] Hitting times, commute times, and cover times for random walks on random hypergraphs
    Helali, Amine
    Loewe, Matthias
    STATISTICS & PROBABILITY LETTERS, 2019, 154
  • [8] The hitting and cover times of random walks on finite graphs using local degree information
    Ikeda, Satoshi
    Kubo, Izumi
    Yamashita, Masafumi
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (01) : 94 - 100
  • [9] Reducing the hitting and the cover times of random walks on finite graphs by local topological information
    Ikeda, S
    Kubo, I
    Yamashita, M
    VLSI'03: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON VLSI, 2003, : 203 - 207
  • [10] The hitting and cover times of random walks on finite graphs using local degree information
    Department of Computer Science and System Engineering, University of Miyazaki, 1-1 Gakuen Kibanadai Nishi, Miyazaki, 889-2192, Japan
    不详
    不详
    Theor Comput Sci, 1 (94-100):
12345