The cover time of sparse random graphs

被引：44
作者：
Cooper, Colin
Frieze, Alan [1 ]
机构：
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
[2] Univ London Goldsmiths Coll, Dept Math & Comp Sci, London SW14 6NW, England
来源：
RANDOM STRUCTURES & ALGORITHMS | 2007年 / 30卷 / 1-2期
关键词：
random walk; random graphs; cover time;
D O I：
10.1002/rsa.20151
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We study the cover time of a random walk on graphs G epsilon G(n,p), when p = c log n /n, c > 1. We prove that whp, the cover time, is asymptotic to c log (c/c-1) n log n. (c) 2006 Wiley Periodicals, Inc.
引用
收藏
页码：1 / 16
页数：16
相关论文
共 50 条
  • [31] Regular pairs in sparse random graphs I
    Kohayakawa, Y
    Rödl, V
    RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (04) : 359 - 434
  • [32] The Cover Time of a Random Walk in Affiliation Networks
    Bloznelis, Mindaugas
    Jaworski, Jerzy
    Rybarczyk, Katarzyna
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2022, 68 (09) : 6134 - 6150
  • [33] The cover time of the giant component of a random graph
    Cooper, Colin
    Frieze, Alan
    RANDOM STRUCTURES & ALGORITHMS, 2008, 32 (04) : 401 - 439
  • [34] Critical random graphs: Diameter and mixing time
    Nachmias, Asaf
    Peres, Yuval
    ANNALS OF PROBABILITY, 2008, 36 (04) : 1267 - 1286
  • [35] LIMITS OF LOCAL ALGORITHMS OVER SPARSE RANDOM GRAPHS
    Gamarnik, David
    Sudan, Madhu
    ANNALS OF PROBABILITY, 2017, 45 (04) : 2353 - 2376
  • [36] Gibbs measures and phase transitions on sparse random graphs
    Dembo, Amir
    Montanani, Andrea
    BRAZILIAN JOURNAL OF PROBABILITY AND STATISTICS, 2010, 24 (02) : 137 - 211
  • [37] UNIVERSALITY FOR FIRST PASSAGE PERCOLATION ON SPARSE RANDOM GRAPHS
    Bhamidi, Shankar
    van der Hofstad, Remco
    Hooghiemstra, Gerard
    ANNALS OF PROBABILITY, 2017, 45 (04) : 2568 - 2630
  • [38] Constraining the clustering transition for colorings of sparse random graphs
    Anastos, Michael
    Frieze, Alan
    Pegden, Wesley
    ELECTRONIC JOURNAL OF COMBINATORICS, 2018, 25 (01)
  • [39] MAXIMUM WEIGHT PARTIAL COLORINGS ON SPARSE RANDOM GRAPHS
    Jaslar, Steven
    Tatikonda, Sekhar
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) : 934 - 955
  • [40] The Cover Time of Cartesian Product Graphs
    Abdullah, Mohammed
    Cooper, Colin
    Radzik, Tomasz
    COMBINATORIAL ALGORITHMS, 2011, 6460 : 377 - 389
12345