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 条
  • [41] Cover time of a random graph with given degree sequence
    Abdullah, Mohammed
    Cooper, Colin
    Frieze, Alan
    DISCRETE MATHEMATICS, 2012, 312 (21) : 3146 - 3163
  • [42] The Flooding Time in Random Graphs
    Remco Van Der Hofstad
    Gerard Hooghiemstra
    Piet van Mieghem
    Extremes, 2002, 5 (2) : 111 - 129
  • [43] MIXING TIME OF NEAR-CRITICAL RANDOM GRAPHS
    Ding, Jian
    Lubetzky, Eyal
    Peres, Yuval
    ANNALS OF PROBABILITY, 2012, 40 (03) : 979 - 1008
  • [44] 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
  • [45] 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
  • [46] Exchangeable random measures for sparse and modular graphs with overlapping communities
    Todeschini, Adrien
    Miscouridou, Xenia
    Caron, Francois
    JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY, 2020, 82 (02) : 487 - 520
  • [47] Cycles of given lengths in unicyclic components in sparse random graphs
    Noy, Marc
    Rasendrahasina, Vonjy
    Ravelomanana, Vlady
    Rue, Juanjo
    ADVANCES IN APPLIED MATHEMATICS, 2021, 125
  • [48] Finding Paths in Sparse Random Graphs Requires Many Queries
    Ferber, Asaf
    Krivelevich, Michael
    Sudakov, Benny
    Vieira, Pedro
    RANDOM STRUCTURES & ALGORITHMS, 2017, 50 (01) : 71 - 85
  • [49] Large Induced Distance Matchings in Certain Sparse Random Graphs
    Tian, Fang
    Sun, Yu-Qin
    Liu, Zi-Long
    GRAPHS AND COMBINATORICS, 2025, 41 (03)
  • [50] On a cover time problem on a dynamic graph with steps at random times
    Demirci, Yunus Emre
    Islak, Umit
    Yildiz, Mehmet Akif
    STATISTICS & PROBABILITY LETTERS, 2023, 197
12345